B. НОД разбиение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Находясь у Киры дома, Джоске увидел на столе лист с написанной на нем задачей.

Задача звучала так. Есть массив $$$a$$$ длины $$$n$$$. На этом массиве нужно сделать следующее:

  • выбрать число $$$k > 1$$$;
  • разбить массив на $$$k$$$ подотрезков $$$^\dagger$$$;
  • посчитать сумму в каждом из $$$k$$$ подотрезков и записать их в другой массив $$$b$$$ (где сумма подотрезка $$$(l, r)$$$ равна $$${\sum_{j = l}^{r}a_j}$$$);
  • итоговым счетом такого разбиения будет $$$\gcd(b_1, b_2, \ldots, b_k)^\ddagger$$$.

Задача заключается в поиске такого разбиения, чтобы счет был максимально возможным. Джоске заинтересовался данной задачей, но не силен в информатике. Помогите ему найти максимально возможный счет.

$$$^\dagger$$$ Разбиением массива на $$$k$$$ подотрезков называется $$$k$$$ пар чисел $$$(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$$$ таких, что $$$l_i \le r_i$$$ и для каждого $$$1 \le j \le k - 1$$$ верно $$$l_{j + 1} = r_j + 1$$$, а также $$$l_1 = 1$$$ и $$$r_k = n$$$. Эти пары представляют сами подотрезки.

$$$^\ddagger$$$ $$$\gcd(b_1, b_2, \ldots, b_k)$$$ обозначает наибольший общий делитель (НОД) массива $$$b$$$.

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

Первая строка содержит единственное число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Для каждого набора данных в первой строке содержится одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9 $$$) — сам массив $$$a$$$.

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

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

Для каждого набора входных данных выведите единственное число — максимальный счет при оптимальном разбиении.

Пример
Входные данные
6
4
2 2 1 3
2
1 2
3
1 4 5
6
1 2 1 1 1 3
10
12 30 37 88 12 78 89 17 2 12
6
7 7 7 7 7 7
Выходные данные
4
1
5
3
1
21
Примечание

В первом наборе входных данных можно выбрать $$$k = 2$$$ и разбить массив на подотрезки $$$(1, 2)$$$ и $$$(3, 4)$$$.

Тогда счет такого разбиения будет равен $$$\gcd(a_1 + a_2, a_3 + a_4) = \gcd(2 + 2, 1 + 3) = \gcd(4, 4) = 4$$$.

В четвертом наборе входных данных можно выбрать $$$k = 3$$$ и разбить массив на подотрезки $$$(1, 2), (3, 5), (6, 6)$$$.

Счётом разбиения будет $$$\gcd(1 + 2, 1 + 1 + 1, 3) = 3$$$.