E. Хорошие тройки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано неотрицательное целое число $$$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$$$. Порядок чисел в тройке имеет значение.

Пример
Входные данные
12
11
0
1
2
3
4
5
3141
999
2718
9999999
10000000
Выходные данные
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)$$$.