C. Разбиение массива
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Аллена есть массив $$$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$$$, тогда все подмассивы будут одинаковыми.

Помогите Аллену найти количество очков, которое он заработает.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество очков, которое заработает Аллен.

Пример
Входные данные
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
Примечание

В первом наборе входных данных $$$k=2$$$ приносит очко, так как Аллен может выбрать $$$m = 2$$$, и оба подмассива будут равны $$$[1, 0]$$$. $$$k=4$$$ также приносит очко, так как независимо от выбора $$$m$$$ у Аллена будет только один подмассив, и следовательно, все подмассивы будут равны.

Во втором наборе входных данных Аллен зарабатывает $$$1$$$ очко при $$$k=3$$$, и при этом выбор $$$m$$$ не имеет значения.