← 返回题目列表

Codeforces · 2148/G

G. 农夫约翰的最后愿望

中文机器翻译题面 查看原题

贝西在地板上发现了一个长度为 $$$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])$$$。

示例

输入
复制

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

输出
复制

0 1 2 3 3 3 4 5 
0 0 0 0 0 0 
0 1 2 2 4 4 4 4 5