给定一个非负整数n (n>=0)。如果 a + b + c = n 和 digsum(a) + digsum(b) + digsum(c) = digsum(n) 是非负整数 (a, b, c) 的三倍，其中 digsum(x)是数字 x 的位数之和，那么 (a, b, c) 就是好数。

例如，如果 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<=t<=100) ，下面是测试用例的说明。
测试用例的第一行，也是唯一一行，包含一个整数 n ( 0<=n<=10000000 )。

对每个测试用例输出一个整数，即给定整数 n 的好三元组数目。

三元组中整数的顺序很重要。