G. Farmer John's Last Wishtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputBessie 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) > \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])$$$.InputThe 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$$$.OutputFor 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])$$$.ExampleInput382 4 3 6 5 7 8 666 6 6 6 6 698 4 2 6 3 9 5 7 8Output0 1 2 3 3 3 4 5
0 0 0 0 0 0
0 1 2 2 4 4 4 4 5