题目描述

对于正整数 $x$ 和 $y$，定义函数 $f(x,y)$ 如下：

将 $x,y$ 用十进制表示成字符串后按此顺序连接，得到字符串 $z$；把 $z$ 作为十进制整数所表示的数就是 $f(x,y)$。例如：$f(3,14)=314$，$f(100,3)=1003$。

给定正整数 $C$ 与 $D$，计数满足以下条件的整数 $x$ 的个数：

• $1\le x\le D$；
• $f(C,C+x)$ 是完全平方数（即某个整数的平方）。

现在有 $T$ 个测试用例，请对每个测试用例输出答案。

输入格式

输入共 $T+1$ 行。

• 第一行包含一个整数 $T$，表示测试用例的数量。
• 接下来每一行表示一个测试用例，包含两个整数 $C$ 和 $D$，即：

输出格式

输出共 $T$ 行。第 $i$ 行（$1\le i\le T$）为第 $i$ 个测试用例的答案：满足条件的 $x$ 的个数。

样例输入

4
4 80
183 5000
18 10
824 5000000000

样例输出

3
2
0
1421

说明

样例解释

对于第一个测试用例，有三个 $x$ 值满足条件： $x = 5, 37, 80$ ;

• 当 $x=5$ 时 , $f(C, C+5) = f(4,9) = 49 = 7^2$;
• 当 $x=37$ 时， $f(C, C+37) = f(4,41) = 441 = 21^2$ ;
• 当 $x=80$ 时， $f(C, C+80) = f(4,84) = 484 = 22^2$ 。

对于第二个测试用例，有两个 $x$ 值满足条件： $x = 1, 3133$ ;

• 当 $x=1$ 时， $f(C, C+1) = f(183,184) = 183184 = 428^2$ ;
• 当 $x=3133$ ， $f(C, C+3133) = f(183,3316) = 1833316 = 1354^2$ 。

对于第三个测试用例，满足条件的 $x$ 值为零。

对于第四个测试用例，有 $1421$ 个 $x$ 值满足条件。

数据范围

• $1\le T\le 3\times 10^{5}$；
• $1\le C\le 2\times 10^{8}$；
• $1\le D\le 5\times 10^{9}$；
• 所有输入值为整数。