[Solution] The Miracle and the Sleeper solution codeforces

The Miracle and the Sleeper solution codeforces


You are given two integers ll and rrlrl≤r. Find the largest possible value of amodbamodb over all pairs (a,b)(a,b) of integers for which rablr≥a≥b≥l.

As a reminder, amodbamodb is a remainder we get when dividing aa by bb. For example, 26mod8=226mod8=2.

Input

Each test contains multiple test cases.

The first line contains one positive integer tt (1t104)(1≤t≤104), denoting the number of test cases. Description of the test cases follows.

The only line of each test case contains two integers llrr (1lr1091≤l≤r≤109).

Output

For every test case, output the largest possible value of amodbamodb over all pairs (a,b)(a,b) of integers for which rablr≥a≥b≥l.

Example The Miracle and the Sleeper solution codeforces
input The Miracle and the Sleeper solution codeforces

Copy The Miracle and the Sleeper solution codeforces
4
1 1
999999999 1000000000
8 26
1 999999999
output

Copy
0
1
12
499999999
Note

In the first test case, the only allowed pair is (a,b)=(1,1)(a,b)=(1,1), for which amodb=1mod1=0amodb=1mod1=0.

In the second test case, the optimal choice is pair (a,b)=(1000000000,999999999)(a,b)=(1000000000,999999999), for which amodb=1amodb=1.

Solution: Click here

The Miracle and the Sleeper solution codeforcessolution codeforcescodeforces solutioncodeforces freshersonline

Leave a Comment