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

Вам даны n целых положительных чисел a1, a2, ..., an.

Для каждого ai требуется найти целое положительное число ki такое, что десятичная запись числа 2ki содержит десятичную запись числа ai среди своих последних min(100, length(2ki)) цифр как подстроку, где length(m) означает длину десятичной записи числа m.

Обратите внимание, что минимизировать ki не обязательно. В рассматриваемых десятичных записях не могут содержаться ведущие нули.

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

В первой строке содержится целое число n (1 ≤ n ≤ 2 000) — количество чисел ai.

В каждой из следующих n строк содержится одно целое число ai (1 ≤ ai < 1011).

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

Выведите n строк: в i-й из них целое число ki такое, что последние min(100, length(2ki)) цифр числа 2ki содержат десятичную запись числа ai как подстроку. Числа ki должны удовлетворять неравенствам 1 ≤ ki ≤ 1050.

Можно показать, что при данных ограничениях ответ всегда существует. Если есть несколько ответов, выведите любой.

Примеры
Входные данные
2
8
2
Выходные данные
3
1
Входные данные
2
3
4857
Выходные данные
5
20