题目内容

我们称一个非负整数为平方数，如果它可以表示为某个整数 $k$ 的平方 $k^2$。例如，前几个平方数是 $0, 1, 4, 9, 16, 25$。

现在定义一种特殊的正整数，称为“双子平方数”。一个正整数 $x$ 是双子平方数，当且仅当：

• $x$ 本身是一个平方数；
• 存在一个分割位置，将 $x$ 的十进制表示分成左右两个非空片段，使得每个片段对应的整数也是平方数；
• 任意一个片段不允许有前导零，除非该片段恰好是单个字符 '0'。

例如，$49$ 可以在 $4$ 和 $9$ 之间分割，分别得到平方数 $4$ 和 $9$，且 $49$ 本身是平方数，因此 $49$ 是一个双子平方数。

现在给定若干上界，请你统计不超过给定上界的双子平方数的个数。

数据范围：测试数据组数 $T$ 不超过 $50$，每个上界 $n$ 不超过 $10^9$。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 50$），表示测试数据组数。接下来 $T$ 行，每行包含一个整数 $n$（$1 \le n \le 10^9$），表示上界。

输出描述

对于每组测试数据，输出一行一个整数，表示不超过 $n$ 的双子平方数的个数。

样例1

输入

1
48

输出

0

说明

对于 $n = 48$，不存在不超过 48 的双子平方数。最小的双子平方数是 $49 = 7^2$，它可以分割为 4 和 9，$4 = 2^2$，$9 = 3^2$，且两段均无前导零，因此 $49$ 是双子平方数，但 $49 > 48$，故答案为 0。

样例2

输入

1
360

输出

2

说明

对于 $n = 360$，不超过 360 的双子平方数有 49 和 169，共 2 个。

其中 $49 = 7^2$ 可分割为 $4$ 和 $9$；$169 = 13^2$ 可分割为 $16$ 和 $9$（$16 = 4^2$，$9 = 3^2$）。下一个双子平方数是 $361 = 19^2$，可分割为 $36$ 和 $1$，但 $361 > 360$，不含在内。

样例3

输入

1
5000

输出

8

说明

对于 $n = 5000$，不超过 5000 的双子平方数共 8 个，按升序排列为：

$49 = 7^2$（分为 $4$ 和 $9$）
$169 = 13^2$（分为 $16$ 和 $9$）
$361 = 19^2$（分为 $36$ 和 $1$）
$1225 = 35^2$（分为 $1$ 和 $225$，$225 = 15^2$）
$1444 = 38^2$（分为 $144$ 和 $4$，$144 = 12^2$）
$1681 = 41^2$（分为 $16$ 和 $81$，$81 = 9^2$）
$3249 = 57^2$（分为 $324$ 和 $9$，$324 = 18^2$）
$4225 = 65^2$（分为 $4$ 和 $225$，$225 = 15^2$）

下一个双子平方数为 $15625 = 125^2$，已超过 $5000$，因此答案为 8。