商店里共有n个模型排成一行摆放在货架上，并依次编号为1，2，3，…,n，它们的尺寸依次分别为s1,s2,s3,……,sn，显然，si表示第i个（编号为i）模型的尺寸。

明明同学想要按照编号递增顺序购买若干个模型。但明明同学想要购买满足下列条件的模型，他将其定义为完美序列模型：

假设所购买的模型序列中任意两个相邻模型的编号依次为i_j和i_j+1（显然有i_j<i_j+1），如果i_j+1能够被i_j整除，且s_ij+1>s_ij，则认为该模型序列是完美的。

例如，对于6个尺寸为{3,6,7,7,7,7}的模型，他可以购买编号为1,2,6的模型，得到的模型序列将是完美的，因为此时有：2可以被1整除，6可以被2整除，且{3，6，7}序列是递增的。

此外，请注意，只购买一个模型的方案也被认为是完美的。

请问明明同学最多可以购买几个模型，使得所购买的模型序列仍然是完美序列。

第一行只有一个整数t(1≤t≤100)：测试用例的数量。

每个测试用例共两行：

第一行只有一个整数n（1≤n≤1e6）：模型的数量；

第二行共n个整数s1,s2,s3,……,sn(1≤si≤1e9)：si为第i个模型的尺寸。