题目描述

对于正整数 $n$，将它的十进制各位从高位到低位依次写成序列。定义 $f(n)$ 为该数位序列的最长严格递增子序列长度。

例如：

• $f(347)=3$；
• $f(1192)=2$；
• $f(10123456789)=10$；
• $f(11111)=1$。

给定正整数 $N$。求有多少个正整数 $x$，能够通过将

重复执行零次或多次后得到 $N$。

共有 $T$ 组测试数据，请分别求解。

限制条件

• $1\le T\le 2\times 10^4$
• $1\le N\le 10^{18}$
• 所有输入均为整数。

输入

T
N_1
N_2
...
N_T

输出

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案。

样例输入 1

6
7
110
1000000000000000000
567784738694904180
555056967895592095
942135357890920474

样例输出 1

7
5
1000000000000000000
23644
22551
60795

例如，对于第二组测试数据，从 $x=102$ 开始反复执行操作可得到

满足条件的 $x$ 只有 $102,104,106,108,110$，共 $5$ 个。