Tạo số chính phương

Cho hai số nguyên \(A\) và \(B\). Hãy tìm số nguyên \(C\) nhỏ nhất thoả mãn đồng thời:

• \(C \ge B\);
• tích \(A \cdot C\) là một số chính phương (bằng \(k^2\) với \(k\) là số nguyên nào đó; số \(0\) cũng được coi là số chính phương).

Nếu không tồn tại \(C\) như vậy, in ra NO SOL.

Có \(T\) bộ dữ liệu cần trả lời độc lập.

Input

• Dòng đầu chứa số nguyên \(T\).
• \(T\) dòng sau, mỗi dòng chứa hai số nguyên \(A\) và \(B\).

Output

Với mỗi bộ dữ liệu in ra một dòng: giá trị \(C\) nhỏ nhất, hoặc NO SOL nếu không có.

Constraints

• \(1 \le T \le 100\).
• \(|A|, |B| \le 10^{18}\).
• Các subtask: (40%) \(0 \le A, B \le 10^5\); (20%) \(0 \le A, B \le 10^9\); (20%) \(|A|, |B| \le 10^9\); (20%) không ràng buộc thêm.

Sample Input 1

4
2 7
18 30
-8 -20
0 -3

Sample Output 1

8
32
-18
-3

Sample Input 2

2
-2 5
5 -4

Sample Output 2

NO SOL
0

Explanation

• \(A=2, B=7\): \(2 \cdot 8 = 16 = 4^2\), còn \(C=7\) cho \(14\) không chính phương.
• \(A=18, B=30\): \(18 \cdot 32 = 576 = 24^2\).
• \(A=-8, B=-20\): \(-8 \cdot (-18) = 144 = 12^2\), và \(-18\) là số nhỏ nhất \(\ge -20\) dùng được.
• \(A=0\): mọi \(C\) đều cho tích \(0\), nên \(C = B\).
• \(A=-2, B=5\): \(C \ge 5\) làm \(A \cdot C < 0\), không thể là số chính phương.
• \(A=5, B=-4\): chọn \(C=0\) (tích bằng \(0\)).