给定一个正整数 $n$。我们称没有前导零的正整数 $a$ 为回文数，如果将其数字顺序反转后仍然与原数相同。请你计算将 $n$ 表示为若干个正回文数之和的不同方案数。若至少有一种回文数的使用次数不同，则认为两种方案不同。例如，$5=4+1$ 和 $5=3+1+1$ 被认为是不同的方案，但 $5=3+1+1$ 和 $5=1+3+1$ 被认为是相同的方案。

形式化地说，你需要计算所有和为 $n$ 的正回文数的不同多重集合的数量。

由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

输入的第一行包含一个整数 $t$（$1\leq t\leq 10^4$），表示测试用例的数量。

每个测试用例包含一行，一个整数 $n$（$1\leq n\leq 4\cdot 10^4$），表示需要用正回文数之和表示的目标数。

输出格式

对于每个测试用例，输出一个整数，表示所需答案对 $10^9+7$ 取模后的结果。

2
5
12

7
74

2
14
5

126
7

3
47
21
27

42901
639
2060

说明/提示

对于第一个测试用例，将 $5$ 拆分为正回文数之和的方案有 $7$ 种：

• $5=1+1+1+1+1$
• $5=1+1+1+2$
• $5=1+2+2$
• $5=1+1+3$
• $5=2+3$
• $5=1+4$
• $5=5$

对于第二个测试用例，将 $12$ 拆分为正整数之和的方案共有 $77$ 种，但其中 $12=2+10$、$12=1+1+10$ 和 $12=12$ 不是有效的回文数拆分方案，因为 $10$ 和 $12$ 不是回文数。因此，将 $12$ 拆分为正回文数之和的方案有 $74$ 种。