write a go solution for 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.

Input Format:
The first line of input contains a single integer t (1<=t<=10^3) denoting the number of test cases.

Each test case contains a single line of input containing two integers x (1<=x<=10^8) and n (1<=n<=x).

Output Format:
For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.

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.. Output only the code with no comments, explanation, or additional text.