5.5 🔢✨ Triple Harmony ✨ 🎶

Score: 25pts

Time Limit: 0.45 sec

Imagine you're a puzzle designer for a popular math magazine. Your latest challenge involves creating a new type of number puzzle called "Triple Harmony." Here's how you explain it to your readers:

Given a non-negative integer n (n ≥ 0), find all "harmonious triples" (a, b, c) that satisfy two conditions:

a + b + c = n

digsum(a) + digsum(b) + digsum(c) = digsum(n)

Where digsum(x) is the sum of digits in number x.

For example, with n = 26, the triple (4, 12, 10) is harmonious because:

4 + 12 + 10 = 26

(4) + (1+2) + (1+0) = (2+6)

Your puzzle asks readers to find the total number of harmonious triples for a given n. Remember, order matters, so (4, 12, 10) and (10, 12, 4) count as different triples.

How many harmonious triples can your readers find for the puzzle number n?

Given a non-negative integer n (n ≥ 0), find all "harmonious triples" (a, b, c) that satisfy two conditions:

a + b + c = n

digsum(a) + digsum(b) + digsum(c) = digsum(n)

Where digsum(x) is the sum of digits in number x.

For example, with n = 26, the triple (4, 12, 10) is harmonious because:

4 + 12 + 10 = 26

(4) + (1+2) + (1+0) = (2+6)

Your puzzle asks readers to find the total number of harmonious triples for a given n. Remember, order matters, so (4, 12, 10) and (10, 12, 4) count as different triples.

How many harmonious triples can your readers find for the puzzle number n?

Constraints

t(1≤t≤10^4)

n(0≤t≤10^7)

n(0≤t≤10^7)

Input Format

The first line of input contains a single integer t— the number of test cases

The first and only line of the test case contains one integer n

The first and only line of the test case contains one integer n

Output Format

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 1

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

Explanation:

there are 12 intances of the numbers, for the first instance i.e 11, there exist 9 harmonious triples

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

Explanation:

there are 12 intances of the numbers, for the first instance i.e 11, there exist 9 harmonious triples