题目描述

我们定义一个整数$x$是一个平方差数，当且仅当存在两个整数$a,b$，满足:$x=a^2−b^2$。

你需要回答$Q$个询问，每次询问会给出两个整数$l,r$，保证$l≤r$。

你需要回答在$l,l+1,l+2,⋯,r−1,r$这$r−l+1$个数字中，有多少个数是平方差数。

输入格式

输入的第一行包括一个正整数$Q$，表示询问的数量。

接下来输入$Q$行，每行两个整数$l,r$，表示一组询问。

输出格式

输入$Q$行，每行一个整数表示询问的答案。

(提示：请使用 long long 类型)

样例

4
2 6
1 19
-3 5
3 45

3
14
7
33

5
-51 65
-48 456
114 514
191 9810
192 60817

88
379
300
7215
45470

5
1 14
5 14
1 91
9 810
-100000 1000000

10
7
68
601
825001

样例说明

样例 1：2 到 6 的答案为 3，其中$3=2^2−1^2，4=2^2−0^2，5=3^2−2^2$共三个。

数据范围

• 对于前 30%的数据，保证$Q≤10, 0≤l,r≤10^2$。
• 对于前60%的数据，保证$Q≤10^3, 0≤l,r≤2*10^5$。
• 另有10%的数据，保证$Q≤10^4, 0≤l,r≤10^9$ 且对于每一组询问，均满足$l=r$。
• 另有10%的数据，保证$Q≤10^4, 0≤l,r≤10^9$ 。
• 对于100%的数据，保证$Q≤10^4, -10^9≤l,r≤10^9$。