CF2148G Farmer John's Last Wish

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]) $ .