ZC是一个爱数数的孩子，他现在自己定义了一种叫做"666"的数，对于一个数x，令S(x)为x的各数位上的数字之和,比如S(123)=1+2+3=6。如果x是“666”数则它要满足
现在给定整数N，ZC想数出[1,N]这个区间内"666"数有多少个。但是无奈这个范围太大了, ZC想了想可能到他的孙子也数不完，于是他向你求助，你能帮助他快速的实现目标吗？你只需输出答案取模$10^{9} + 7$之后的结果。
第一行一个整数$T$代表有$T$组询问($1 \le T \le 1000$)。
接下来T行，每行一个整数$N$($1 \le N \le 10^{50}$)。
输出T行，第i行代表第i个询问的答案。
输入的N保证无前导0