数字与平方根

时间限制：2s
空间限制：1024MB

题目描述

你需要处理 $T$ 组测试。对于每组测试，给定一个整数 $N$，求满足以下条件的整数 $x$ 的个数：

• $1\le x\le N$；
• 记 $y=\lfloor\sqrt{x}\rfloor$。将 $x$ 和 $y$ 不含前导零地写成十进制数字后，$y$ 是 $x$ 的前缀。

输入格式

第一行一个整数 $T$。

接下来 $T$ 行，第 $i$ 行一个整数 $N_i$。

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试的答案。

样例输入 1

2
1
174

样例输出 1

1
22

数据范围

• $1\le T\le 10^5$；
• $1\le N_i\le 10^{18}$。