Problem Description

kuro想考考Toya有关数正方体的问题，然而Toya只会数数，不会几何，kuro只好换了一道数数题。

对于$[0,10^{10}]$范围以内的正整数，数位和为$k$的数有多少个？

Toya数了很久，发现根本数不过来！她想在下次见到kuro的时候回答这个问题，希望你能帮帮她。

数位和指一个数的各个十进制位上的数的和，例如114514的数位和为16

Input Format

第一行为一个正整数$T(1 \leq T \leq 10^5)$,表示该测试点的测试数据组数

接下来的$T$行，每行有一个数字$k(0 \leq k \leq 10^{18})$，表示询问数位和为$k$的数字有多少个

Output Format

共输出$T$行，每行有一个数字$S$,表示数位和为$k$的数字个数

Sample

输入 #1

5
0
1
2
3
4

输出 #1

1
11
55
220
715

样例解释

数位和为0的数只有一个，即0

Hint

提示:如果你的数学很好，可以尝试使用纯数学知识解决该题目