G. Последнее желание фермера Джона
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бесси нашла массив $$$a$$$ длины $$$n$$$ на полу. Рядом с массивом лежит рукописная записка, предположительно написанная фермером Джоном. В записке написано:

Помоги мне, дорогая Бесси! Пусть $$$f(a)$$$ обозначает максимальное целое число $$$k$$$ в диапазоне $$$[1,n)$$$ такое, что $$$\gcd(a_1, a_2, \ldots, a_k) \gt \gcd(a_1, a_2, \ldots, a_{k+1})$$$, или $$$0$$$, если такого $$$k$$$ не существует.

Бесси решает помочь ФД. Она определяет $$$g(a)$$$ как максимальное значение $$$f(a)$$$ для всех возможных перестановок $$$a$$$.

Бесси решает не только найти $$$g(a)$$$, но и значение $$$g(p)$$$ для всех префиксов $$$p$$$ массива $$$a$$$. Выведите $$$n$$$ целых чисел, $$$i$$$-е из которых равно $$$g([a_1, a_2, \ldots, a_i])$$$.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$)  — количество наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, разделенных пробелами ($$$1 \leq a_i \leq n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел в новой строке: $$$i$$$-е из которых должно быть равно $$$g([a_1, a_2, \ldots, a_i])$$$.

Пример
Входные данные
3
8
2 4 3 6 5 7 8 6
6
6 6 6 6 6 6
9
8 4 2 6 3 9 5 7 8
Выходные данные
0 1 2 3 3 3 4 5 
0 0 0 0 0 0 
0 1 2 2 4 4 4 4 5