Dora 有一个包含整数的集合 $$$s$$$。一开始,她会将$$$[l, r]$$$中的所有整数放入集合$$$s$$$中。也就是说,当且仅当 $$$l \leq x \leq r$$$ 时,整数 $$$x$$$ 最初包含在集合中。然后她允许您执行以下操作:
- 从集合 $$$s$$$ 中选择三个不同的整数 $$$a$$$、$$$b$$$ 和 $$$c$$$,使得 $$$\gcd(a, b) = \gcd(b, c) = \gcd(a, c) = 1^\dagger$$$。
- 然后,从集合 $$$s$$$ 中删除这三个整数。
您最多可以执行多少次操作?
$$$^\dagger$$$回想一下 $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq 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$$$的操作。