Codeforces Round 921 (Div. 2) |
---|
Finished |
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≤t≤103) denoting the number of test cases.
Each test case contains a single line of input containing two integers x (1≤x≤108) and n (1≤n≤x).
For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.
310 35 5420 69
2 1 6
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.
Name |
---|