Лорд Омкар разрешил тебе войти в Храм Омкара! Чтобы проверить, достоин ли ты, Омкар дает тебе пароль, который ты должен понять!
Пароль представляет собой массив \(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\)) операций?
Выходные данные
Для каждого пароля выведите одно целое число — наименьшую возможную длину пароля после некоторого количества операций.
Примечание
В первом наборе входных данных вы можете сделать следующее для достижения длины в \(1\):
Выберите \(i=2\), чтобы получить \([2, 4, 1]\).
Выберите \(i=1\), чтобы получить \([6, 1]\).
Выберите \(i=1\), чтобы получить \([7]\).
Во втором наборе входных данных вы не можете выполнить ни одной операции, потому что нет \(i\), которые удовлетворяли бы вышеперечисленным требованиям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
2 1 3 1
2
420 420
|
1
2
|