G. Farmer John's Last Wish
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie has found an array $$$a$$$ of length $$$n$$$ on the floor. There appears to be a handwritten note lying next to the array, seemingly written by Farmer John. The note reads:

Help me, dear Bessie! Let $$$f(a)$$$ denote the maximum integer $$$k$$$ in the range $$$[1,n)$$$ such that $$$\gcd(a_1, a_2, \ldots, a_k) \gt \gcd(a_1, a_2, \ldots, a_{k+1})$$$, or $$$0$$$ if no such $$$k$$$ exists.

Bessie decides to help FJ. She defines $$$g(a)$$$ to represent the maximum value of $$$f(a)$$$ over all possible reorderings of $$$a$$$.

Bessie decides to not only find $$$g(a)$$$, but also the value of $$$g(p)$$$ for all prefixes $$$p$$$ of $$$a$$$. Output $$$n$$$ integers, the $$$i$$$'th of which is $$$g([a_1, a_2, \ldots, a_i])$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$)  — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

The following line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers on a new line: the $$$i$$$'th of which should be $$$g([a_1, a_2, \ldots, a_i])$$$.

Example
Input
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
Output
0 1 2 3 3 3 4 5 
0 0 0 0 0 0 
0 1 2 2 4 4 4 4 5