CF2007A Dora's Set

Dora has a set $ s $ containing integers. In the beginning, she will put all integers in $ [l, r] $ into the set $ s $ . That is, an integer $ x $ is initially contained in the set if and only if $ l \leq x \leq r $ . Then she allows you to perform the following operations: - Select three distinct integers $ a $ , $ b $ , and $ c $ from the set $ s $ , such that $ \gcd(a, b) = \gcd(b, c) = \gcd(a, c) = 1^\dagger $ . - Then, remove these three integers from the set $ s $ . What is the maximum number of operations you can perform? $ ^\dagger $ Recall that $ \gcd(x, y) $ means the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ .

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 500 $ ) — the number of test cases. The description of the test cases follows. The only line of each test case contains two integers $ l $ and $ r $ ( $ 1 \leq l \leq r \leq 1000 $ ) — the range of integers in the initial set.

For each test case, output a single integer — the maximum number of operations you can perform.

In the first test case, you can choose $ a = 1 $ , $ b = 2 $ , $ c = 3 $ in the only operation, since $ \gcd(1, 2) = \gcd(2, 3) = \gcd(1, 3) = 1 $ , and then there are no more integers in the set, so no more operations can be performed. In the second test case, you can choose $ a = 3 $ , $ b = 5 $ , $ c = 7 $ in the only operation. In the third test case, you can choose $ a = 11 $ , $ b = 19 $ , $ c = 20 $ in the first operation, $ a = 13 $ , $ b = 14 $ , $ c = 15 $ in the second operation, and $ a = 10 $ , $ b = 17 $ , $ c = 21 $ in the third operation. After the three operations, the set $ s $ contains the following integers: $ 12 $ , $ 16 $ , $ 18 $ . It can be proven that it's impossible to perform more than $ 3 $ operations.