Turtle and GCD
Description
This problem was supposed to have a cool statement but I forgot to add it.
Given two numbers $a$ and $b$, consider the set of integers $a$, $a + 1$, $a + 2$, …, $a + b - 1$. Partition this set into two nonempty sets such that each element belongs to exactly one set and the GCD of the sum of the sets is maximized. What is that maximum GCD?
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.
The first line contains two space separated integers $a$ and $b$ ($1 \le a \le 10^4$, $2 \le b \le 10^4$).
It is guaranteed that the sum of $a$ over all test cases is at most $10^4$.
It is also guaranteed that the sum of $b$ over all test cases is at most $10^4$.
For each test case, output a single line, the maximum possible GCD.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.
The first line contains two space separated integers $a$ and $b$ ($1 \le a \le 10^4$, $2 \le b \le 10^4$).
It is guaranteed that the sum of $a$ over all test cases is at most $10^4$.
It is also guaranteed that the sum of $b$ over all test cases is at most $10^4$.
Output
For each test case, output a single line, the maximum possible GCD.
6
11 4
3 3
1 6
25 36
6253 9564
69 420
25
4
7
765
52766979
58485
Note
In the first test case, the numbers are $[11, 12, 13, 14]$ which we can partition into $[11, 14]$ and $[12, 13]$. The sum of the sets are $11 + 14 = 25$ and $12 + 13 = 25$ and GCD$(25, 25) = 25$. Guys after reading this, please be sure to orz Richard (both of them).
In the second test case, the set of numbers is $[3, 4, 5]$ which we partition into $[3, 5]$ and $[4]$. The sum of the subsets are $3 + 5 = 8$ and $4$ and GCD$(4, 8) = 4$.