Description

X是一个正整数，它的第i个数字是d[i]，则 序列（d [1]，d[2]，d[3]，…，d[t]）是X的数字
表示（没有前导零）。特别地，d[1]是最高位数字并且d[t]是X的最低位数字。例如，X =576的数字表示是（5,7,6）。我们说整数X是魔术数，当且仅当：
1、X是某个整数的平方，即对于某个整数Y ，X = Y * Y。
2、对于X 的数字表示（d[1]，d[2]，d[3]，…，d[t]），它满足d[1] < d[2] > d[3] <d[4]……，依此类推。也就是说，对于每个奇数下标i < t，满足d[i] < d[i+1]，并且对于每个偶数下标i < t，它满足d[i] > d[i+1]。给定A和B，输出A和B之间有多少魔术数。

Input Format

多组测试数据。
第一行，一个整数G，表示有G组测试数据。1 <= G <= 10。
每组测试数据格式：
一行，两个整数A和B。 1 <= B <= 10^10。 1 <= A <= B 。

Output Format

共G行，每行一个整数。

3
1 64
50 60
121 121

7
0
1

Source

南海区镇赛 桂城小学2018A 前缀和 二分查找