B'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 <= q t <= q 10^3 ) denoting the number of test cases. Each test case contains a single line of input containing two integers x ( 1 <= q x <= q 10^8 ) and n ( 1 <= q n <= q x ). For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve. 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 . '...