1602 喜欢数学的P同学

题目描述

在紫金学院中，擅长数学的P同学设计了一个数学游戏，游戏规则如下：

给定一个由 $lns="http://www.w3.org/1998/Math/MathML"> n$ 个正整数组成的序列 $lns="http://www.w3.org/1998/Math/MathML"> a$ ，P同学需要为序列的每一个n的正因子 $lns="http://www.w3.org/1998/Math/MathML"> k$ k 进行以下操作：

分割序列：将序列 $lns="http://www.w3.org/1998/Math/MathML"> a$ 分成 $lns="http://www.w3.org/1998/Math/MathML"> \frac{n}{k}$ 个长度为 $lns="http://www.w3.org/1998/Math/MathML"> k$ 的子串，这些子串互不重叠。例如，第一个子串是 $lns="http://www.w3.org/1998/Math/MathML"> [a_{1}, a_{2}, \dots, a_{k}]$ ，第二个子串是 $lns="http://www.w3.org/1998/Math/MathML"> [a_{k + 1}, a_{k + 2}, \dots, a_{2 k}]$ ，依此类推，直到最后一个子串 $lns="http://www.w3.org/1998/Math/MathML"> [a_{n - k + 1}, a_{n - k + 2}, \dots, a_{n}]$ 。
模数变换：P同学选择一个整数 $lns="http://www.w3.org/1998/Math/MathML"> m \geq 2$ ，将序列 $lns="http://www.w3.org/1998/Math/MathML"> a$ 中的每一个元素 $lns="http://www.w3.org/1998/Math/MathML"> a_{i}$ 替换为 $lns="http://www.w3.org/1998/Math/MathML"> a_{i} m o d m$ 。
子串匹配：如果经过模数变换后，所有分割得到的子串都完全相同，那么P同学就获得一分。

最后需要求出P同学最终获得了多少分。

输入格式

每个测试由多个测试用例组成。
第一行包含一个整数 (1

lns="http://www.w3.org/1998/Math/MathML">

≤t≤10⁴ ) - 测试用例数。
每个测试用例的第一行包含一个整数

(1≤n≤2 ⋅ 10⁵) -数组

的长度。
每个测试用例的第二行包含

个整数( 1≤a_i≤n ) - 数组

的元素。
保证所有测试用例中

lns="http://www.w3.org/1998/Math/MathML">

的总和不超过

。

输出格式

对于每个测试用例，输出一个整数,代表P同学的最终得分

样例输入

8
4
1 2 1 4
3
1 2 3
5
1 1 1 1 1
6
1 3 1 1 3 1
6
6 2 6 2 2 2
6
2 6 3 6 6 6
10
1 7 5 1 4 3 1 3 1 4
1
1

样例输出

提示/说明

在第一个测试样例当中，k = 2 得一分，因为P同学可以选择m = 2，而且两个子数组都等于[1 , 0]。 k = 4也可以得一分，因为无论m取多少，都只有一个子数组，因此所有的子数组都相等。
在第二个测试样例当中，k = 3 得一分，无论m可以取多少。