题目描述

Dora 有一个整数集合 $s$。在最开始，她会将所有满足 $l\le x\le r$ 的整数 $x$ 放入 $s$ 中。然后她允许你进行如下操作：

• 首先，在 $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$），表示开始时集合中的整数范围。

输出格式

对于每组数据，输出一个整数，代表你所能进行的最大操作次数。

样例解释翻译

在第一组数据中，你只能进行一次操作，且这次操作中只能选择 $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$ 进行第三次操作。在三次操作后，集合 $s$ 中剩余 $12,16,18$ 这三个整数。可以证明你最多只能进行 $3$ 次操作。

样例

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