斐波那契数列是一个众所周知的整数序列，其中 $F_0 = 0, F_1 = 1$ 且对于 $n > 1$ 有 $F_n = F_{n-1} + F_{n-2}$。
Lesha 不喜欢这个序列，也不喜欢所有可以通过删去若干位数字后得到正斐波那契数的整数 $x$。例如，Lesha 不喜欢数字 193，因为删去 9 后可以得到 $F_6 = 13$。
你的任务是找出从 0 到 $n$ 之间 Lesha 喜欢的整数个数。
输入格式
第一行包含一个整数 $t$ —— 测试用例的数量。
接下来的 $t$ 行，每行包含一个整数 $n$ —— 你需要统计 Lesha 喜欢的数字的上限。
$1 \le t \le 10$ $0 \le n \le 10^{18}$
输出格式
输出 $t$ 行，每行包含一个整数 —— 对应测试用例的答案。
样例
输入 1
2 4 2019
输出 1
2 125
说明
在第一个测试用例中，符合条件的数字是 0 和 4。