该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

仲夏这个月的生活费又花超了，于是仲夏打算在网上买面包来吃，一天吃三个（这样就有钱充月卡了）。

题目描述

仲夏有一个面包袋 s 。一开始，他会将手中的面包从 l到r 依次进行编号（编号均为整数）， 然后再将所有面包放入袋子 s。也就是说，当且仅当 $l \leq x \leq r$ 时，编号为 x 的面包初始装在袋子中。但是仲夏觉得单纯一个一个吃面包太无趣了，于是他想用以下操作来吃面包：

• 从袋子 s 中选择三个编号分别为a，b，c 的面包 ，并使得 gcd( a , b ) = gcd( b , c ) = gcd( a , c ) = 1。
• 然后，今天就从袋子 s 中拿出这三个面包吃掉。

最多可以进行多少次上述操作？

输入格式

每个测试由多个测试用例组成。第一行包含一个整数 t （ $1 \leq t \leq 500$ ） - 测试用例数。测试用例说明如下。

每个测试用例的唯一一行包含两个整数 l 和 r （ $1 \leq l \leq r \leq 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 的运算。

限制

每次测试时间限制：1秒

每次测试的内存限制：256 MB