11889 - Benefit

兩個整數A, B的最小公倍數C，可用下列等式表示：LCM(A, B) = C。本題給定A, C，請你找出B。

Input

輸入的第一列為整數T(T <= 100000)表示測試資料的組數，每組資料一列包含兩個整數A, C(1 <= A, C <= 10,000,000)。

Output

每組測試資料一列，請輸出最小的整數B使得LCM(A, B) = C。若B不存在則請輸出"NO SOLUTION"。

Sample Input 

3
2 6
32 1760
7 16

Sample Output 

3
55
NO SOLUTION

---

原文出處