#P2194. 特殊爱好

特殊爱好

    你们zkc学长有一个特别的爱好(gj ? no ),他特别喜好一种数。

    这种数有一下几种特征

    1. 必须以2开头,比如 222333333

    2. 这个数前i位的和必定能被第i位整除( 1<= i <=x,     x为该数的位数,比如222333333

    3. 每个数中肯定没有1,0,这两个数字,比如222333333

    好了,现在,zkc学长想要问你了,1到n中有多少这种的数。

Input

T(<=20)组数据
n(1 <= n <= 1e15)

Output

x 表示 1到n(包括1和n)中有多少个这种数。

Sample Input

2
1
2

Sample Output

0
1

HINT

Source