A16451. 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.

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

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

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