题目描述

我们定义一个函数 $f(x)$（$x$ 是正整数）如下：将 $x$ 的十进制表示的所有数字倒序排列，然后去掉前导零。例如，$f(321) = 123$，$f(120) = 21$，$f(1000000) = 1$，$f(111) = 111$。

我们再定义另一个函数 $g(x) = \dfrac{x}{f(f(x))}$（$x$ 也是正整数）。

你的任务如下：对于给定的正整数 $n$，计算所有满足 $1 \le x \le n$ 的 $x$ 中，$g(x)$ 可能取到的不同值的个数。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。

每个测试用例包含一行，一个整数 $n$（$1 \le n < 10^{100}$）。该整数没有前导零。

输出格式

对于每个测试用例，输出一个整数，表示当 $x$ 取遍 $[1, n]$ 时，函数 $g(x)$ 可能取到的不同值的个数。

说明/提示

示例中前两个测试用例的解释：

1. 如果 $n = 4$，那么对于每个 $1 \le x \le n$ 的整数，$\dfrac{x}{f(f(x))} = 1$；
2. 如果 $n = 37$，那么对于某些 $1 \le x \le n$ 的整数，$\dfrac{x}{f(f(x))} = 1$（例如 $x = 23$，$f(f(x)) = 23$，$\dfrac{x}{f(f(x))} = 1$）；对于其他一些 $x$，$\dfrac{x}{f(f(x))} = 10$（例如 $x = 30$，$f(f(x)) = 3$，$\dfrac{x}{f(f(x))} = 10$）。因此，$g(x)$ 可能取到两种不同的值。

由 ChatGPT 4.1 翻译

样例

5
4
37
998244353
1000000007
12345678901337426966631415

1
2
9
10
26