题目描述

多拉有一个集合s，包含整数。开始时，她将区间[l, r]中的所有整数放入集合s中。也就是说，整数x初始包含在集合中，当且仅当l≤x≤r。然后，她允许你执行以下操作：

从集合s中选择三个不同的整数a、b和c，使得gcd(a, b)=gcd(b, c)=gcd(a, c)=1。然后，从集合s中移除这三个整数。你可以执行的最大操作次数是多少？

注意：gcd(x, y)表示整数x和y的最大公约数。

输入

每个测试由多个测试用例组成。第一行包含一个整数t（1≤t≤500）——测试用例的数量。测试用例的描述如下。

每个测试用例的唯一一行包含两个整数l和r（1≤l≤r≤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 进行第三次操作。经过这三次操作，集合 s 包含以下整数：12, 16, 18。可以证明无法进行超过 3 次操作。