Codeforces Round 919 (Div. 2) |
---|
Finished |
Allen has an array a1,a2,…,an. For every positive integer k that is a divisor of n, Allen does the following:
Help Allen find the number of points he will earn.
Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤2⋅105) — the length of the array a.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n) — the elements of the array a.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
For each test case, output a single integer — the number of points Allen will earn.
841 2 1 431 2 351 1 1 1 161 3 1 1 3 166 2 6 2 2 262 6 3 6 6 6101 7 5 1 4 3 1 3 1 411
2 1 2 4 4 1 2 1
In the first test case, k=2 earns a point since Allen can pick m=2 and both subarrays will be equal to [1,0]. k=4 also earns a point, since no matter what m Allen chooses, there will be only one subarray and thus all subarrays are equal.
In the second test case, Allen earns 1 point for k=3, where his choice for m does not matter.
Name |
---|