codeforces#P1925B. A Balanced Problemset?
A Balanced Problemset?
Description
Jay managed to create a problem of difficulty $x$ and decided to make it the second problem for Codeforces Round #921.
But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of $n$ sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to $x$.
The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset.
Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.
The first line of input contains a single integer $t$ ($1\leq t\leq 10^3$) denoting the number of test cases.
Each test case contains a single line of input containing two integers $x$ ($1\leq x\leq 10^8$) and $n$ ($1\leq n\leq x$).
For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.
Input
The first line of input contains a single integer $t$ ($1\leq t\leq 10^3$) denoting the number of test cases.
Each test case contains a single line of input containing two integers $x$ ($1\leq x\leq 10^8$) and $n$ ($1\leq n\leq x$).
Output
For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.
3
10 3
5 5
420 69
2
1
6
Note
For the first test case, one possible way is to break up the problem of difficulty $10$ into a problemset having three problems of difficulties $4$, $2$ and $4$ respectively, giving a balance equal to $2$.
For the second test case, there is only one way to break up the problem of difficulty $5$ into a problemset of $5$ problems with each problem having a difficulty $1$ giving a balance equal to $1$.