406554: GYM102439 H Nonfibonacci numbers

Fibonacci numbers — well-known integer sequence, where $$$F_0 = 0$$$, $$$F_1 = 1$$$ and $$$F_n = F_{n - 1} + F_{n - 2}$$$ for $$$n > 1$$$.

Lesha doesn't like this sequence and all the numbers $$$x$$$, such that we can get positive Fibonacci number by crossing out several digits. For example, Lesha doesn't like number $$$193$$$, because it is possible to cross $$$9$$$ out and get $$$F_6 = 13$$$.

Your task is to find the number of integers from $$$0$$$ to $$$n$$$ which Lesha likes.

The first line contains a single integer $$$t$$$ — the number of test cases.

Each of the following $$$t$$$ lines contains a single integer $$$n$$$ — number, until which you have to count numbers which Lesha likes.

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

Print $$$t$$$ lines, each of them should contain a single integer — the answer for the test case.

2
4
2019

2
125

In the first test suitable numbers are 0 and 4.