题目描述

我们说一个正整数 $X$ 是魔术数，当且仅当：

1. $X$ 是某个整数的平方，即存在整数 $Y$ 使得 $X = Y \times Y$；
2. 记 $X$ 的数字表示为 $(d_1, d_2, d_3, \dots, d_t)$（没有前导零，$d_1$ 是最高位，$d_t$ 是最低位），该序列满足如下交替大小关系：$$d_1 < d_2 > d_3 < d_4 > d_5 < \dots$$ 也就是说，从第一位开始，奇数位小于相邻的偶数位，偶数位大于相邻的奇数位。若位数 $t=1$，则无需比较，视为满足条件。

给定 $A$ 和 $B$，请你计算在 $A$ 和 $B$ 之间（包含 $A, B$）有多少个魔术数。

输入格式

第一行一个整数 $G$，表示测试数据组数（$1 \le G \le 10$）。
接下来 $G$ 行，每行包含两个整数 $A$ 和 $B$，表示一组询问。

输出格式

对于每组询问，输出一行一个整数，表示区间 $[A, B]$ 中魔术数的个数。

样例

3
1 64
50 60
121 121

7
0
1

数据范围

• $1 \le G \le 10$
• $1 \le A \le B \le 10^{10}$