模型选择 - 代码源竞赛平台

题目描述

蜗蜗有 $n$ 个模型，模型编号从 1 到 $n$，第 $i$ 个模型的尺寸为 $s_i$。

他想从中选出若干个模型，并按照编号递增的顺序排列。对于相邻选中的两个模型，后一个模型的编号必须是前一个模型编号的倍数，并且后一个模型的尺寸必须严格更大。

请你求出最多能选出多少个模型。

输入格式

第一行包含一个整数 T，表示测试用例数量。

对于每组测试用例：

• 第一行包含一个整数 $n$；
• 第二行包含 $n$ 个整数 $s_1,s_2,\ldots,s_n$。

输出格式

对于每组测试用例，输出一行一个整数，表示最多能选出的模型数量。

样例

1
6
1 2 3 4 8 16

3

样例解释

可以选择编号为 1、2、4 的模型，它们的编号满足倍数关系，尺寸 1、2、4 也严格递增，因此可以选出 3 个模型。

数据范围

对于 100% 的数据，保证 $1\le T\le100$，所有测试用例的 $n$ 之和不超过 $10^5$，$1\le n\le10^5$，$1\le s_i\le10^9$。