题目描述

请针对 $T$ 个测试用例，回答以下问题。

给定一个整数 $N$，请计算满足以下所有条件的整数 $x$ 的个数：

• $1 \leq x \leq N$
• 令 $y = \lfloor \sqrt{x} \rfloor$。此时，将 $x$ 和 $y$ 都用十进制（且不含前导 $0$）表示时，$y$ 是 $x$ 的前缀。

输入格式

输入以如下格式从标准输入读入。

$T$ $N_1$ $N_2$ $\vdots$ $N_T$

其中，$N_i$ 表示第 $i$ 个测试用例中的整数 $N$。

输出格式

请输出共 $T$ 行。
第 $i$ 行输出第 $i$ 个测试用例的答案，结果为一个整数。

样例 1

输入

2
1
174

输出

1
22

说明/提示

限制条件

• $T$ 是满足 $1 \leq T \leq 10^5$ 的整数。
• $N$ 是满足 $1 \leq N \leq 10^{18}$ 的整数。

样例解释 1

本输入包含 $2$ 个测试用例。

• 对于第 $1$ 个测试用例，$x=1$ 时，$y = \lfloor \sqrt{1} \rfloor = 1$，满足题目中的条件。
• 对于第 $2$ 个测试用例，例如 $x=100$，$y = \lfloor \sqrt{100} \rfloor = 10$，满足题目中的条件。

由 ChatGPT 4.1 翻译