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) > \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)). 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). 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)).