Кратос нашел книгу, в которой описан таинственный ритуал. Изначально можно выбрать любое число $$$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