令 $m(x)$ 为正整数 $x$ 在十进制表示下各位数字的众数。众数是指在序列中出现次数最多的数值中最大的那个。例如，$m(15532) = 5$，$m(25252) = 2$，$m(103000) = 0$，$m(364364) = 6$，$m(114514) = 1$，$m(889464) = 8$。

给定一个正整数 $n$，DreamGrid 想知道 $(\sum_{x=1}^{n} m(x)) \pmod{10^9 + 7}$ 的值。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个不含前导零的正整数 $n$ ($1 \le n < 10^{50}$)。

保证所有测试数据的 $|n|$ 之和不超过 $50$，其中 $|n|$ 表示 $n$ 在十进制表示下的位数。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示 $(\sum_{x=1}^{n} m(x)) \pmod{10^9 + 7}$ 的值。

样例

输入格式 1

5
9
99
999
99999
999999

输出格式 1

45
615
6570
597600
5689830