贝西在地板上发现了一个长度为 $$$n$$$ 的数组 $$$a$$$。阵列旁边似乎有一张手写的便条,似乎是农夫约翰写的。注释中写道:
帮助我,亲爱的贝西!令 $$$f(a)$$$ 表示 $$$[1,n)$$$ 范围内的最大整数 $$$k$$$,使得 $$$\gcd(a_1, a_2, \ldots, a_k) \gt \gcd(a_1, a_2, \ldots, a_{k+1})$$$,或 $$$0$$$(如果不存在这样的 $$$k$$$)。
贝西决定帮助 FJ。她定义 $$$g(a)$$$ 来表示 $$$f(a)$$$ 在所有可能的 $$$a$$$ 重新排序中的最大值。
Bessie 决定不仅要查找 $$$g(a)$$$,还要查找 $$$a$$$ 的所有前缀 $$$p$$$ 的 $$$g(p)$$$ 的值。输出$$$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])$$$。
示例
输入复制
382 4 3 6 5 7 8 666 6 6 6 6 698 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