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

Мальчик Биньямин очень любит единицы, даже слишком, поэтому психологи решили, что он болеет «Единоманией». Для того, чтобы разнообразить его любовь к цифрам, врачи попросили найти квадарт числа состоящего из $$$k$$$ единиц. Так как врачи не готовы слушать Биньямина вечность, было принято решение, что если числа в итоговом числе идут подряд и повторяются, то их можно сократить, к примеру $$$1299999994444442$$$ можно заменить на $$$129x74x62$$$, $$$121212121212$$$ на $$$(12)x6$$$, а $$$11$$$ на $$$1x2$$$. Требуется найти ответ минимальной длины для $$$t$$$ вариантов $$$k$$$.

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

В первой строке вводится число $$$t$$$ ($$$1$$$ $$$\le$$$ $$$t$$$ $$$\le$$$ $$$10^4$$$). В последующих $$$t$$$ строках вводится число $$$k$$$ ($$$0$$$ $$$\le$$$ $$$k$$$ $$$\le$$$ $$$10^9$$$).

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

В $$$t$$$ строках выведите ответы на задачу. Считайте, что если $$$k = 0$$$, ответ на задачу $$$1$$$.

Система оценки

В этой задаче каждый тест оценивается независимо и стоит 1 балл.

Примеры

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

    512345

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

    1
    121
    12321
    1234321
    123454321

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

    3302

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

    12321
    1
    121