AT_ndpc2026_p.LIS

For a positive integer $n$, define $f(n)$ as follows:

• Let $n$ have $d$ digits in decimal representation. Define a sequence $A = (A_1, \dots, A_d)$ of length $d$ as follows:
  • $A_i$ is the $i$-th digit from the left in the decimal representation of $n$.
• Let $f(n)$ be the length of the longest strictly increasing subsequence of $A$.

For example, $f(347) = 3$, $f(1192) = 2$, $f(10123456789) = 10$, and $f(11111) = 1$.

You are given a positive integer $N$.
Count the number of positive integers $x$ such that by repeatedly applying the operation $x \to x + f(x)$ zero or more times, you can obtain $N$.

You are given $T$ test cases. Solve each of them.

对于正整数 $n$，定义函数 $f(n)$ 如下：

• 设 $n$ 的十进制表示包含 $d$ 位数字。定义一个长度为 $d$ 的序列 $A = (A_1, \dots, A_d)$：
  • $A_i$ 是 $n$ 的十进制表示中从左往右第 $i$ 位数字。
• 令 $f(n)$ 为序列 $A$ 的最长严格递增子序列的长度。

例如，$f(347) = 3$，$f(1192) = 2$，$f(10123456789) = 10$，以及 $f(11111) = 1$。

给定一个正整数 $N$。
请统计满足如下条件的正整数 $x$ 的个数：通过将操作 $x \to x + f(x)$ 执行零次或多次，可以得到 $N$。

你将收到 $T$ 组测试用例，请对每组用例求解。

The input is given from standard input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例按以下格式给出：

$N$

Print $T$ lines. On the $i$-th line, output the answer for the $i$-th test case.

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。

Sample 1 Explanation:
For example, in the second test case, starting from $x = 102$ and repeatedly applying the operation $x \to x + f(x)$:

• $102 \to 104 \to 106 \to 108 \to 110$

we can obtain $N = 110$. The only values of $x$ satisfying the condition are $x = 102, 104, 106, 108, 110$, so there are $5$ in total.

Constraints

• $1 \leq T \leq 2 \times 10^4$
• $1 \leq N \leq 10^{18}$
• All input values are integers

样例 1 解释：
例如，在第二个测试用例中，从 $x = 102$ 开始，反复执行操作 $x \to x + f(x)$：

• $102 \to 104 \to 106 \to 108 \to 110$

即可得到 $N = 110$。满足条件的 $x$ 值仅有 $x = 102,\, 104,\, 106,\, 108,\, 110$，共 $5$ 个。

约束条件

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