E. Good Triples

Given a non-negative integer number $n$ ($n \ge 0$). Let's say a triple of non-negative integers $(a, b, c)$ is good if $a + b + c = n$, and $digsum(a) + digsum(b) + digsum(c) = digsum(n)$, where $digsum(x)$ is the sum of digits of number $x$.

For example, if $n = 26$, then the pair $(4, 12, 10)$ is good, because $4 + 12 + 10 = 26$, and $(4) + (1 + 2) + (1 + 0) = (2 + 6)$.

Your task is to find the number of good triples for the given number $n$. The order of the numbers in a triple matters. For example, the triples $(4, 12, 10)$ and $(10, 12, 4)$ are two different triples.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Descriptions of test cases follow.

The first and only line of the test case contains one integer $n$ ($0 \le n \le 10^7$).

Output

For each test case output one integer, the number of good triples for the given integer $n$. Order of integers in a triple matters.

Example

input

12
11
0
1
2
3
4
5
3141
999
2718
9999999
10000000

output

9
1
3
6
10
15
21
1350
166375
29160
1522435234375
3

Note

In the first example, the good triples are $(0, 0, 11)$, $(0, 1, 10)$, $(0, 10, 1)$, $(0, 11, 0)$, $(1, 0, 10)$, $(1, 10, 0)$, $(10, 0, 1)$, $(10, 1, 0)$, $(11, 0, 0)$.

In the second example, there is only one good triple $(0, 0, 0)$.

解题思路

  比 G 题难，G 都做出来了这题还不会。

  如果没观察出 $a+b+c$ 有进位则必然有 $digsum(a) + digsum(b) + digsum(c) > digsum(n)$ 那就真别想做出来了。假设 $x$ 在十进制下有 $n$ 个数位，表示成 $x_{n-1}x_{n-2} \ldots x_{0}$，同理将 $a$，$b$，$c$ 用 $n$ 个数位来表示，不足用前导零补。如果每一个数位都不产生进位，即对于 $i \in [0,n-1]$，都有 $a_i + b_i + c_i < 10$，那么 $digsum(a) + digsum(b) + digsum(c) = digsum(n)$ 就等价于对于每个 $i \in [0, n-1]$ 都有 $a_i + b_i + c_i = x_i$。否则如果某一位产生了进位，那么 $digsum(a_i) + digsum(b_i) + digsum(c_i) = a_i + b_i + c_i >  digsum(x_i)$，两位数肯定大于一位数，因此必然有 $digsum(a) + digsum(b) + digsum(c) > digsum(n)$。

  为此我们只需单独考虑 $a$，$b$，$c$ 的每一位选哪些数即可，即求 $a_i + b_i + c_i = x_i$ 的非负整数解的数量。可以用隔板法，不过隔板法求的是正整数解的数量，只需让 $a_i$，$b_i$，$c_i$ 都加一个偏移量即可，即 $a'_i = a_i + 1$，$b'_i = b_i + 1$，$c'_i = c_i + 1$，那么等式就变成 $a'_i + b'_i + c'_i = x_i + 3$，因此解的数量就是 $C_{x_i + 2}^{2}$。因此最终答案就是 $\prod\limits_{i=0}^{n-1}{C_{x_i + 2}^{2}}$。

  AC 代码如下，时间复杂度为 $O(\log{n})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

void solve() {
    int x;
    scanf("%d", &x);
    LL ret = 1;
    while (x) {
        int t = x % 10;
        x /= 10;
        ret *= (t + 2ll) * (t + 1) >> 1;
    }
    printf("%lld\n", ret);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    
    return 0;
}

参考资料

  Codeforces Round 913 (Div. 3) Editorial：https://codeforces.com/blog/entry/123012