1907E.md (1551B)
1 Source: https://codeforces.com/problemset/problem/1907/E 2 3 E. Good Triples 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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)$. 24 25 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. 26 27 Input 28 29 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. 30 31 The first and only line of the test case contains one integer $n$ ($0 \le n \le 10^7$). 32 33 Output 34 35 For each test case output one integer, the number of good triples for the given integer $n$. Order of integers in a triple matters. 36 37 Example 38 39 Input 40 41 ``` 42 12 43 44 11 45 46 0 47 48 1 49 50 2 51 52 3 53 54 4 55 56 5 57 58 3141 59 60 999 61 62 2718 63 64 9999999 65 66 10000000 67 ``` 68 69 Output 70 71 ``` 72 9 73 1 74 3 75 6 76 10 77 15 78 21 79 1350 80 166375 81 29160 82 1522435234375 83 3 84 ``` 85 86 Note 87 88 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)$. 89 90 In the second example, there is only one good triple $(0, 0, 0)$.