HZNUOJ

How many 666 ?

Tags:
Time Limit:  2 s      Memory Limit:   256 MB
Submission:115     AC:40     Score:100.00

Description

ZC是一个爱数数的孩子,他现在自己定义了一种叫做"666"的数,对于一个数x,令S(x)为x的各数位上的数字之和,比如S(123)=1+2+3=6。如果x是“666”数则它要满足

  1. x是正整数且无前导0。
  2. x(mod 666) = S(x)。
  3. 6在x这个数的各数位上出现的总次数必须为奇数。

现在给定整数N,ZC想数出[1,N]这个区间内"666"数有多少个。但是无奈这个范围太大了, ZC想了想可能到他的孙子也数不完,于是他向你求助,你能帮助他快速的实现目标吗?你只需输出答案取模$10^{9} + 7$之后的结果。

Input

第一行一个整数$T$代表有$T$组询问($1 \le T \le 1000$)。

接下来T行,每行一个整数$N$($1 \le N \le 10^{50}$)。

Output

输出T行,第i行代表第i个询问的答案。

Samples

input
3 666 1000 10000
output
1 10 55

Hint

输入的N保证无前导0

Author

QIU, Longfeng