7 月 12 日

题目描述

Dshawn 有个可爱的妹子，妹子生日是 $7$ 月 $12$ 号。Dshawn 想知道，$1$ 到 $N$ 的整数中有多少个数字，满足数字十进制表示里的每一个连续子串既不是 $7$ 也不是 $12$ 的倍数。Dshawn 把这种数字成为 Eva 数。

比如 $1111111114111111$ 和 $19244$ 这两个数就不是 Eva 数，因为第一个数中 $14$ 是 $7$ 的倍数，第二个数中 $24$ 是 $12$ 的倍数。

友情提示， $0$ 也是 $7$ 和 $12$ 的倍数，所以满足条件的数字中也不能包含 $0$。

输入

第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。

接下来依次给出每组测试数据。

每组数据仅一行，包含一个整数 $N$，含义见题目描述。

保证数据满足 $1 \leq T \leq 10^{5},$ $1 \leq N \leq 10^{18}$。

输出

对于每组数据，输出一行，包含一个整数，代表 $1$ 到 $N$ 中有多少个 Eva 数。

输入样例

2
7
100

输出样例

6
56

样例解释

对于第二组样例，$1$ 到 $100$ 中的 Eva 数 有 $1, 2, 3, 4, 5, 6, 8, 9,$ $11, 13, 15, 16, 18, 19,$ $22, 23, 25, 26, 29,$ $31, 32, 33, 34, 38, 39,$ $41, 43, 44, 45, 46,$ $51, 52, 53, 54, 55, 58, 59,$ $61, 62, 64, 65, 66, 68, 69,$ $81, 82, 83, 85, 86, 88, 89,$ $92, 93, 94, 95$ 和 $99$。