A. Dora 的集合

时间限制：1 秒
内存限制：256 MB

Dora 有一个包含整数的集合 $s$。一开始，她会把 $[l, r]$ 中的所有整数放入集合 $s$。也就是说，一个整数 $x$ 最初在集合中当且仅当 $l \le x \le r$。然后她允许你执行以下操作：

从集合 $s$ 中选择三个互不相同的整数 $a$、$b$ 和 $c$，使得 $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$†。
然后，从集合 $s$ 中移除这三个整数。

你能执行的最大操作次数是多少？

† 回顾：$\gcd(x,y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试用例的数量。

每个测试用例只有一行，包含两个整数 $l$ 和 $r$（$1 \le l \le r \le 1000$）—— 初始集合中整数的范围。

输出格式

对于每个测试用例，输出一个整数 —— 你能执行的最大操作次数。

示例

输入

8
1 3
3 7
10 21
2 8
51 60
2 15
10 26
1 1000

输出

1
1
3
1
2
3
4
250

样例解释

第一个测试用例：你可以选择 $a=1$、$b=2$、$c=3$ 进行一次操作，因为 $\gcd(1,2)=\gcd(2,3)=\gcd(1,3)=1$，之后集合中不再有整数，因此无法进行更多操作。

第二个测试用例：你可以选择 $a=3$、$b=5$、$c=7$ 进行一次操作。

第三个测试用例：你可以先选择 $a=11$、$b=19$、$c=20$，然后选择 $a=13$、$b=14$、$c=15$，最后选择 $a=10$、$b=17$、$c=21$。三次操作后，集合中还剩下 $12$、$16$、$18$。可以证明无法进行超过 $3$ 次操作。