Числа Фибоначчи — известная последовательность чисел, в которой $$$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.
