Perfect Groups

SaMer는 자신의 문제 중 하나를 위해 역사상 가장 훌륭한 테스트 케이스를 작성했다. 주어진 정수 배열에 대해, 같은 그룹에 속한 임의의 정수 쌍의 곱이 완전제곱수가 되도록 배열을 나눌 수 있는 그룹 수의 최솟값을 구하는 문제이다.

각 정수는 정확히 하나의 그룹에 속해야 한다. 하지만 한 그룹에 속한 정수들이 배열에서 반드시 연속할 필요는 없다.

SaMer는 이미 가진 테스트 케이스로부터 더 많은 케이스를 만들고자 한다. 그의 테스트 케이스에는 n개의 정수로 이루어진 배열 A가 있으며, 1 이상 n 이하인 각 정수 k에 대해 문제의 답이 k인 A의 연속 부분 배열 수를 구해야 한다.

입력의 첫 번째 줄에는 배열의 크기를 나타내는 정수 하나 n (1 ≤ n ≤ 5000)가 주어진다.

두 번째 줄에는 배열의 값인 n개의 정수 $a_1$,$a_2$,...,$a_n$ (-$10^8$ ≤ $a_i$ ≤ $10^8$)가 주어진다.

공백으로 구분된 n개의 정수를 출력한다. k-th번째 정수는 문제의 답이 k인 A의 연속 부분 배열 수여야 한다.