Description

给你一个正整数$n(n≤4 \times 10^4​)$。如果某个正整数a在颠倒其数字的顺序后保持不变，则称其为不带前导零回文的整数。找出将n表示为正回文整数之和的不同方式的数量。

如果至少一个回文整数的频率不同，则两种方式被认为是不同的。例如，5=4+1和5=3+1+1被认为是不同的，但5=3+1+1和5=1+3+1被认为是相同的。

Input Format

第一行输入一个正整数$t(t≤10​^4)$表示有t组测试数据

接下来t行每行仅有一行为正整数n，含义如题面所示。

Output Format

对于每组测试输出输出一个整数表示答案，为防止答案超过long long范围，请输出答案对1000000007取模后的结果。

1
5​

7​

Hint

5的7种表示方式如下:

5=1+1+1+1+1

5=1+1+1+2

5=1+1+3

5=1+2+2

5=2+3

5=1+4

5=5