Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

B. A Balanced Problemset?
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

The first line of input contains a single integer t (1t103) denoting the number of test cases.

Each test case contains a single line of input containing two integers x (1x108) and n (1nx).

Output

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

Example
Input
3
10 3
5 5
420 69
Output
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.