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^\dagger$。
• 然后，将这三个整数从集合 $s$ 中移除。

你最多可以进行多少次操作？

$^\dagger$回想一下，$\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 500$) — 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的唯一一行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le 1000$) — 初始集合中整数的范围。

输出格式

对于每个测试用例，输出一个整数 — 你最多可以进行的操作次数。

样例

输入样例 1

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

输出样例 1

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 次操作。