The number of number

Description

定义 $F(x)$ 为十进制正整数 $x$ 中出现次数最多的数的最大值（即对于出现次数相同的数，选取更大的一个）。

例如：$F(12345) = 5, F(112233) = 3, F(102000) = 0$ 。

求解：$\sum_{x = 1}^{n} F(x)$ 的值。由于这个数字可能较大，将结果对 $10^9 +7$ 取模。

Input Format

含有多个测试用例。第一行输入一个整数 T ，代表测试用例的数量。

对于每个测试用例，第一行输入一个不含前导零的正整数 $n$ ，含义与上文一致。

保证所有测试用例 $|n|$ 的总和不会超过 $50$ ，其中 $|n|$ 表示十进制正整数 n 的位数。

Output Format

对于每个测试用例，输出一行包含一个整数，含义见题目描述。

Input Example#1

5
9
99
999
99999
999999

Output Example#1

45
615
6570
597600
5689830

Data Range

$1≤n<10^{50}$ ，保证所有测试用例 $|n|$ 的总和不会超过 $50$ ，其中 $|n|$ 表示十进制正整数 n 的位数。