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

Кратос нашел книгу, в которой описан таинственный ритуал. Изначально можно выбрать любое число $$$n$$$. С ним следует производить следующие действия:

Ритуал продолжается бесконечно, в книге написано, что наименьшее число, которому будет равно $$$n$$$ в процессе этого ритуала — магическое. Кратос пока не определился с тем, какое изначальное $$$n$$$ выбрать. Помогите ему для каждого начального варианта определить соответствующее магическое число.

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

В первой строке дано одно число $$$t$$$ — количество тестов ($$$1 \le t \le 100\,000$$$).

В следующих $$$t$$$ строках даны тесты. Тест содержит одно целое число $$$n_i$$$ — начальное значение $$$n$$$ в $$$i$$$-м тесте ($$$1 \le n_i < 10^{500\,001}$$$).

Суммарная длина чисел во всех тестах не превышает $$$500\,000$$$.

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

Для каждого теста выведите на новой строке одно число — минимальное значение, которому когда-либо будет равно $$$n$$$ в процессе ритуала.

Пример

Входные данные
4
2
3
6
10
Выходные данные
1
3
3
1