← 返回题目列表

AtCoder · arc174_d

D. 数字与平方根

中文机器翻译题面 查看原题

分数: 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.