题目背景

$Papyrus$ 出了一道关于平方差的题目， 快看看啊。

题目描述

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

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

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

输入格式

输入的第一行包括一个正整数$Q(1 \le Q \le 10^4)$，表示询问的数量。

接下来输入$Q$行，每行两个整数$l,r(-10^9 \le l \ le r \le 10^9)$，表示一组询问。

输出格式

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

样例

输入数据 1

4
2 6
1 19
-3 5
3 45

输出数据 1

3
14
7
33

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