给定一个非负整数 $$$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)$$$。