← 返回题目列表

Codeforces · 1350/B

B. Orac 和模型

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

店里有$$$n$$$型号,编号从$$$1$$$到$$$n$$$,尺寸为$$$s_1、s_2、\ldots、s_n$$$。

Orac 将购买一些型号,并按数字递增的顺序排列它们(即索引,但不是尺寸)。

Orac认为得到的排列是漂亮的,如果对于任何两个索引为$$$i_j$$$和$$$i_{j+1}$$$的相邻模型(注意$$$i_j < i_{j+1}$$$,因为Orac正确排列它们),$$$i_{j+1}$$$可以被$$$i_j$$$整除并且$$$s_{i_j} < s_{i_{j+1}}$$$。

例如,对于尺寸为$$$\{3, 6, 7, 7, 7, 7\}$$$的$$$6$$$模型,他可以购买索引为$$$1$$$、$$$2$$$、$$$6$$$的模型,得到的排列会很漂亮。另外,请注意,只有一个模型的排列也被认为是漂亮的。

Orac 想知道他可以购买的最大型号数,他可能会多次询问您这些问题。

输入

第一行包含一个整数 $$$t\ (1 \le t\le 100)$$$:查询次数。

每个查询包含两行。第一行包含一个整数 $$$n\ (1\le n\le 100\,000)$$$:商店中模型的数量,第二行包含 $$$n$$$ 整数 $$$s_1,\dots,s_n\ (1\le s_i\le 10^9)$$$:模型的尺寸。

保证$$$n$$$的总和最多为$$$100\,000$$$。

输出

打印$$$t$$$行,其中第$$$i$$$行应包含Orac可以为第$$$i$$$查询购买的最大模型数量。

示例

输入 #1

4
4
5 3 4 6
7
1 4 2 3 6 4 9
5
5 4 3 2 1
1
9

输出 #1

2
3
1
1

注意

例如,在第一个查询中,Orac 可以购买索引为 $$$2$$$ 和 $$$4$$$ 的模型,排列会很漂亮,因为 $$$4$$$ 可以被 $$$2$$$ 整除,并且 $$$6$$$ 大于 $$$3$$$。通过列举,我们不难发现,不存在超过两个模型的优美排列。

在第二个查询中,Orac 可以购买索引为 $$$1$$$、$$$3$$$ 和 $$$6$$$ 的模型。通过列举,我们不难发现,不存在超过三个模型的优美排列。

在第三个查询中,没有超过一个模型的漂亮安排。