У Аллена есть массив \(a_1, a_2,\ldots,a_n\). Для каждого положительного целого числа \(k\), которое является делителем \(n\), Аллен делает следующее:
- Он разбивает массив на \(\frac{n}{k}\) непересекающихся подмассивов длины \(k\). Другими словами, он разбивает массив на следующие подмассивы: \(\)[a_1,a_2,\ldots,a_k],[a_{k+1}, a_{k+2},\ldots,a_{2k}],\ldots,[a_{n-k+1},a_{n-k+2},\ldots,a_{n}]\(\)
- Аллен получает одно очко, если существует некоторое положительное целое число \(m\) (\(m \geq 2\)), такое что, если он заменит каждый элемент массива на его остаток при делении на \(m\), тогда все подмассивы будут одинаковыми.
Помогите Аллену найти количество очков, которое он заработает.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество очков, которое заработает Аллен.
Примечание
В первом наборе входных данных \(k=2\) приносит очко, так как Аллен может выбрать \(m = 2\), и оба подмассива будут равны \([1, 0]\). \(k=4\) также приносит очко, так как независимо от выбора \(m\) у Аллена будет только один подмассив, и следовательно, все подмассивы будут равны.
Во втором наборе входных данных Аллен зарабатывает \(1\) очко при \(k=3\), и при этом выбор \(m\) не имеет значения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
2
1
2
4
4
1
2
1
|