310909: CF1907E. Good Triples

E. Good Triplestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExampleInput

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)$.

题目大意：
给定一个非负整数n（n≥0）。如果非负整数三元组(a, b, c)满足a + b + c = n，并且digsum(a) + digsum(b) + digsum(c) = digsum(n)，其中digsum(x)是数字x的各位数字之和，则称该三元组为好三元组。

例如，如果n = 26，那么三元组(4, 12, 10)是好三元组，因为4 + 12 + 10 = 26，且(4) + (1 + 2) + (1 + 0) = (2 + 6)。

你的任务是找到给定数字n的好三元组的数量。三元组中的数字顺序是有区别的。例如，三元组(4, 12, 10)和(10, 12, 4)是两个不同的三元组。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。
每个测试用例只有一行，包含一个整数n（0≤n≤10^7）。

输出：
对于每个测试用例，输出一个整数，表示给定整数n的好三元组的数量。

示例：
输入：
```
12
11
0
1
2
3
4
5
3141
999
2718
9999999
10000000
```
输出：
```
9
1
3
6
10
15
21
1350
166375
29160
1522435234375
3
```题目大意： 给定一个非负整数n（n≥0）。如果非负整数三元组(a, b, c)满足a + b + c = n，并且digsum(a) + digsum(b) + digsum(c) = digsum(n)，其中digsum(x)是数字x的各位数字之和，则称该三元组为好三元组。 例如，如果n = 26，那么三元组(4, 12, 10)是好三元组，因为4 + 12 + 10 = 26，且(4) + (1 + 2) + (1 + 0) = (2 + 6)。 你的任务是找到给定数字n的好三元组的数量。三元组中的数字顺序是有区别的。例如，三元组(4, 12, 10)和(10, 12, 4)是两个不同的三元组。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例只有一行，包含一个整数n（0≤n≤10^7）。 输出： 对于每个测试用例，输出一个整数，表示给定整数n的好三元组的数量。 示例： 输入： ``` 12 11 0 1 2 3 4 5 3141 999 2718 9999999 10000000 ``` 输出： ``` 9 1 3 6 10 15 21 1350 166375 29160 1522435234375 3 ```