← 返回题目列表

Codeforces · 1603/A

A. 可分割的混乱

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

YouKn0wWho 有一个整数序列 $$$a_1, a_2, \ldots, a_n$$$。他将执行以下操作,直到序列变空:选择一个索引 $$$i$$$,使得 $$$1 \le i \le |a|$$$ 且 $$$a_i$$$ 不能被 $$$(i + 1)$$$ 整除,并从序列中删除该元素。这里 $$$|a|$$$ 是操作时序列 $$$a$$$ 的长度。请注意,序列 $$$a$$$ 发生了变化,并且下一个操作将在此变化的序列上执行。

例如,如果$$$a=[3,5,4,5]$$$,那么他可以选择$$$i = 2$$$,因为$$$a_2 = 5$$$不能被$$$i+1 = 3$$$整除。执行此操作后,序列为 $$$[3,4,5]$$$。

帮助 YouKn0wWho 确定是否可以使用上述操作擦除整个序列。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以使用上述操作擦除整个序列,则打印“YES”(不带引号),否则打印“NO”(不带引号)。您可以打印任何寄存器(上部或下部)中的每个字母。

示例

输入 #1

5
3
1 2 3
1
2
2
7 7
10
384836991 191890310 576823355 782177068 404011431 818008580 954291757 160449218 155374934 840594328
8
6 69 696 69696 696969 6969696 69696969 696969696

输出 #1

YES
NO
YES
YES
NO

注意

在第一个测试用例中,YouKn0wWho 可以执行以下操作(擦除的元素带有下划线): $$$[1, \underline{2}, 3] \rightarrow [\underline{1}, 3] \rightarrow [\underline{3}] \rightarrow [\,].$$$

在第二个测试用例中,不可能擦除序列,因为$$$i$$$只能是$$$1$$$,并且当$$$i=1$$$时,$$$a_1 = 2$$$可以被$$$i + 1 = 2$$$整除。