分数: 500 点
问题陈述
解决以下问题 T 测试用例。
给定一个整数 N,查找整数的个数 x 满足以下所有条件:
- 1 \le x \le N
- 让 y = \lfloor \sqrt{x} \rfloor。当 x 和 y 以十进制表示法(不带前导零), y 是前缀 x.
约束
- T 是一个整数,使得 1 \le T \le 10^5.
- N 是一个整数,使得 1 \le N \le 10^{18}.
输入
输入由标准输入按以下格式给出:
T N_1 N_2 \vdots N_T
在这里, N_i 代表整数 N 为 总共 i- 第一个测试用例。
输出
打印 T 行。 的 i- 第行应包含以下问题的答案 i- 第一个测试用例作为整数。
示例输入 1
2 1 174
示例输出 1
1 22
此输入包含两个测试用例。
- 对于第一个测试用例, x=1 满足条件,因为 y = \lfloor \sqrt{1} \rfloor = 1.
- 对于第二个测试用例,例如, x=100 满足条件,因为 y = \lfloor \sqrt{100} \rfloor = 10.