Xhesica有一个集合 $S$ 用于存放一些正整数,一开始，$S$ 为空集 ，他首先将所有的位于 $l$ 和 $r$ 之间的整数插入集合 $S$ ,即满足当且仅当整数 $x$ 满足 $l\leq x \leq r$ 时，整数 $x$ 会被加入于集合中。随后,Xhesica允许你进行接下来的操作:
选择仍然存在于集合中的三个不同的整数 $a,b,c$，满足 $\mathrm{gcd}(a,b)=\mathrm{gcd}(a,c)= \mathrm{gcd} (b,c)=1$，之后将这三个整数从集合中删去。
理论上最多能进行多少次操作呢?
注意，$\mathrm{gcd}(a,b)$ 指的是 $a$ 和 $b$ 的最大公因数。
本题目包括多个测试用例，测试用例之间互相独立。
第一行仅有一个正整数 $t$,满足 $1\leq t\leq 500$ ,表示测试用例的数量
接下来有 $t$ 行，每行表示一个测试用例，每行包括两个正整数 $l,r$ 满足 $1\leq l\leq r\leq10^{8}$ ，表示含义同题目描述。
对于每一个测试用例，输出一行，仅包括一个整数，表示本测试用例下你能进行的最多的操作次数。
8
1 3
3 7
10 21
2 8
51 60
2 15
10 26
1 10001
1
3
1
2
3
4
250 对于测试用例 $1$，可以选择 $a=1，b=2，c=3$，之后集合变为空集，无法进行更多的操作。
对于测试用例 $2$, 可以选择 $a=3，b=5，c=7$ ,之后集合中仅剩下 $4,6$，无法进行更多的操作。