← 返回题目列表

Codeforces · 1907/E

E. 好三元组

中文机器翻译题面 查看原题

给定一个非负整数 $$$n$$$ ($$$n \ge 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 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$0 \le n \le 10^7$$$)。

输出

对于每个测试用例输出一个整数,即给定整数 $$$n$$$ 的良好三元组的数量。三元组中整数的顺序很重要。

示例

输入 #1

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

输出 #1

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

注意

在第一个示例中,好的三元组是 $$$(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)$$$。

在第二个示例中,只有一个好的三元组 $$$(0, 0, 0)$$$。