Cho hai số nguyên dương \(n\) và \(k\). Tìm số nguyên dương \(x\) nhỏ nhất thỏa mãn \(x\) là ước của \(n\) và \(\frac{n}{x}≤k\).

Input

• Dòng thứ nhất chứa số \(t(1\leq t\leq100)\) - Số testcase.
• \(t\) dòng tiếp theo, mỗi dòng chứa một cặp \(n(1\leq n\leq10^9)\) và \(k(1\leq k\leq10^9)\) cách nhau bởi dấu cách.

Output

• Gồm \(t\) dòng, mỗi dòng in ra đáp án của từng testcase.

Example

1 
8 7 

2