Codeforces Round 969 (Div. 2) |
---|
Finished |
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≤x≤r. Then she allows you to perform the following operations:
What is the maximum number of operations you can perform?
^\daggerRecall that \gcd(x, y) means the 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.
81 33 710 212 851 602 1510 261 1000
1 1 3 1 2 3 4 250
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.
Name |
---|