Question
Gap Quest
Alice is tasked with finding the largest integer K for given integers X and Y (2 ≤ X, Y ≤ 109), such that she can build a binary string S that has:
- Exactly X zeros;
- Exactly Y ones;
- At least K ones between any two zeros in S.
Input
The first line contains a single integer T, denoting the number of test cases.
The first and only line of each test case contains two integers X and Y − the number of 0's and 1's in S.
The first and only line of each test case contains two integers X and Y − the number of 0's and 1's in S.
Output
For each test case, output on a new line, the largest integer K, such that a binary string satisfies given conditions.
Example
Sample Input
3
2 10
3 2
10 5
Sample Output
10
1
0
Explanation
Test case 1: The ideal binary string would be 011111111110 with 10 occurrences of 1 between two 0s.
Test case 2: The ideal binary string would be 01010 with at least 1 occurrence of 1 between any two 0s.
3
2 10
3 2
10 5
Sample Output
10
1
0
Explanation
Test case 1: The ideal binary string would be 011111111110 with 10 occurrences of 1 between two 0s.
Test case 2: The ideal binary string would be 01010 with at least 1 occurrence of 1 between any two 0s.