«Все-все! Идеальный урок Дореми по математике уже начинается! Присаживайтесь и хорошо поработайте, если хотите иметь такой же IQ, как у меня!» На сегодняшнем уроке Дореми обучает всех вычитанию. И прямо сейчас она дает вам задание, чтобы проверить, насколько вы внимательно слушаете.
Вам дано множество \(S\), содержащее положительные целые числа. Вы можете выполнить следующую операцию несколько (возможно, ноль) раз:
- выбрать два целых числа \(x\) и \(y\) из множества \(S\) такие, что \(x > y\) и \(x - y\) не принадлежит множеству \(S\).
- добавить \(x-y\) в множество \(S\).
Вам нужно сказать Дореми, какое максимальное количество чисел может быть в \(S\), если выполнять все операции оптимально. Можно показать, что это количество ограничено.
Выходные данные
Для каждого набора входных данных вам нужно вывести максимально возможное количество чисел в \(S\). Можно показать, что это количество ограничено.
Примечание
В первом примере не существует подходящих \(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\) чисел.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
1 2
3
5 10 25
|
2
5
|