SaMer написал лучший тест всех времён и народов для одной из его задач. В этой задаче требуется для данного массива целых чисел найти минимальное число групп, на которое можно разбить данный массив так, что произведение любых двух чисел в одной группе — точный квадрат.
Каждое целое число должно находиться ровно в одной группе, однако числа в группе не обязательно должны быть последовательными в массиве.
SaMer хочет создать больше тестов из того теста, который у него уже есть. Его тест является массивом \(A\) из \(n\) целых чисел и ему необходимо найти число подмассивов \(A\), состоящих из чисел, идущих в изначальном массиве последовательно, таких, что ответ на задачу для подмассива будет равен \(k\), для всех \(k\) от \(1\) до \(n\) включительно.
Выходные данные
Выведите \(n\) целых чисел, разделённых пробелами, \(k\)-е из которых должно быть равно числу подмассивов \(A\), состоящих из чисел, идущих в изначальном массиве последовательно, ответ для которых на задачу равен \(k\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 5
|
3 0
|
|
2
|
5
5 -4 2 1 8
|
5 5 3 2 0
|
|
3
|
1
0
|
1
|