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

«Все-все! Идеальный урок Дореми по математике уже начинается! Присаживайтесь и хорошо поработайте, если хотите иметь такой же IQ, как у меня!» На сегодняшнем уроке Дореми обучает всех вычитанию. И прямо сейчас она дает вам задание, чтобы проверить, насколько вы внимательно слушаете.

Вам дано множество $$$S$$$, содержащее положительные целые числа. Вы можете выполнить следующую операцию несколько (возможно, ноль) раз:

  • выбрать два целых числа $$$x$$$ и $$$y$$$ из множества $$$S$$$ такие, что $$$x > y$$$ и $$$x - y$$$ не принадлежит множеству $$$S$$$.
  • добавить $$$x-y$$$ в множество $$$S$$$.

Вам нужно сказать Дореми, какое максимальное количество чисел может быть в $$$S$$$, если выполнять все операции оптимально. Можно показать, что это количество ограничено.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_1 < a_2 < \cdots < a_n \le 10^9$$$) — положительные числа в $$$S$$$.

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

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

Для каждого набора входных данных вам нужно вывести максимально возможное количество чисел в $$$S$$$. Можно показать, что это количество ограничено.

Пример
Входные данные
2
2
1 2
3
5 10 25
Выходные данные
2
5
Примечание

В первом примере не существует подходящих $$$x$$$ и $$$y$$$. Максимальное количество чисел в $$$S$$$ равно $$$2$$$.

Во втором примере:

  • Изначально $$$S=\{5,10,25\}$$$. Можно выбрать $$$x=25$$$, $$$y=10$$$ и добавить $$$x-y=15$$$ в множество.
  • Теперь $$$S=\{5,10,15,25\}$$$. Можно выбрать $$$x=25$$$, $$$y=5$$$ и добавить $$$x-y=20$$$ в множество.
  • Теперь $$$S=\{5,10,15,20,25\}$$$. Теперь нельзя выполнить никакую операцию.

После выполнения этих операций $$$S$$$ будет содержать $$$5$$$ чисел. Можно показать, что не существует последовательности операций, после которой в $$$S$$$ будет более $$$5$$$ чисел.