H. Числа Нефибоначчи
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Числа Фибоначчи — известная последовательность чисел, в которой $$$F_0 = 0$$$, $$$F_1 = 1$$$, а $$$F_n = F_{n - 1} + F_{n - 2}$$$ для $$$n \gt 1$$$.

Леша противится этой последовательности и всех таких чисел $$$x$$$, из которых может получиться положительное число Фибоначчи путем вычеркивания некоторых цифр. Например, Леше противно число $$$193$$$, так как можно вычеркнуть $$$9$$$ и получить $$$F_6 = 13$$$.

Вам требуется найти количество чисел от $$$0$$$ до $$$n$$$, которые не противны Леше.

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

В первой строке входного файла содержится одно целое число $$$t$$$ — количество тестов.

В следующих $$$t$$$ строках содержится по одному целому числу $$$n$$$ — число, до которого необходимо найти количество чисел, не противных Леше.

$$$$$$1 \le t \le 10$$$$$$ $$$$$$0 \le n \le 10^{18}$$$$$$

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

Выходной файл должен содержать $$$t$$$ строк, каждая из которых содержит по одному целому числу — ответу на тест.

Пример
Входные данные
2
4
2019
Выходные данные
2
125
Примечание

В первом тесте подходящими числами являются 0 и 4.