[ARC174] D - Digit vs Square Root

D - Digit vs Square Root

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 500 分

题面

解决以下问题，共有 个测试案例。

给定整数 ，找出满足以下条件的整数 的个数：

• 设 。当以十进制表示 和 时（不带前导零）， 是 的前缀。

限制条件

• 是整数，满足 。
• 是整数，满足 。

---

输入

从标准输入中以以下格式给出：

其中， 表示第 个测试案例的整数 。

输出

共输出 行。第 行应包含第 个测试案例的答案，作为一个整数。

---

输入样例 1

2
1
174

输出样例 1

1
22

此输入包含两个测试案例。

• 对于第一个测试案例， 满足条件，因为 。
• 对于第二个测试案例，例如， 满足条件，因为 。