A. Омкар и пароль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лорд Омкар разрешил тебе войти в Храм Омкара! Чтобы проверить, достоин ли ты, Омкар дает тебе пароль, который ты должен понять!

Пароль представляет собой массив $$$a$$$ из $$$n$$$ положительных целых чисел. Вы можете применить к массиву следующую операцию: выбрать любые два соседних числа, которые не равны друг другу, и заменить их на их сумму. Формально, вы должны выбрать индекс $$$i$$$ такой, что $$$1 \leq i < n$$$ и $$$a_{i} \neq a_{i+1}$$$, удалить $$$a_i$$$ и $$$a_{i+1}$$$ с массива, и на их место вставить $$$a_{i}+a_{i+1}$$$.

Например, для массива $$$[7, 4, 3, 7]$$$ можно выбрать $$$i = 2$$$ и массив станет равным $$$[7, 4+3, 7] = [7, 7, 7]$$$. Обратите внимание, что в этом массиве уже не получится применить данную операцию.

Обратите внимание, что одна операция уменьшает длину пароля на $$$1$$$. Какую наименьшую длину пароля можно получить после некоторого количества (возможно $$$0$$$) операций?

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

Каждый тест содержит несколько наборов входных данных. В первой строке указано количество наборов входных данных $$$t$$$ ($$$1 \le t \le 100$$$). Описание наборов входных данных приведено ниже.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$1 \leq a_{i} \leq 10^9$$$) — начальное содержимое вашего пароля.

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

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

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

Пример
Входные данные
2
4
2 1 3 1
2
420 420
Выходные данные
1
2
Примечание

В первом наборе входных данных вы можете сделать следующее для достижения длины в $$$1$$$:

Выберите $$$i=2$$$, чтобы получить $$$[2, 4, 1]$$$.

Выберите $$$i=1$$$, чтобы получить $$$[6, 1]$$$.

Выберите $$$i=1$$$, чтобы получить $$$[7]$$$.

Во втором наборе входных данных вы не можете выполнить ни одной операции, потому что нет $$$i$$$, которые удовлетворяли бы вышеперечисленным требованиям.