Hôm nay Minh phải trông em thay cho cô của mình. Các em của Minh rất nghịch nên Minh định dùng kẹo để dỗ chúng. Minh có tất cả ~N~ viên kẹo và ~M~ người em. Tuy nhiên với tính nghịch ngợm sẵn có, bọn trẻ yêu cầu số lượng kẹo của các em phải đôi một khác nhau (mỗi em được ít nhất một viên) và Minh phải chia hết ~N~ viên kẹo. Hãy giúp Minh chia kẹo sao cho ước chung lớn nhất của số kẹo của các em là lớn nhất và cho biết giá trị đó.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~T~ là số test ~(T \le 100)~.

• Trong ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~N~ và ~M~ ~(1 \le N, M \le 10^9)~.

Kết quả

• In ra ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả tương ứng của test đó. Nếu không có kết quả in -1.

Ví dụ

Sample Input

2
6 3
6 2

Sample Output

1
2

Chấm điểm

• Subtask 1 (50% số test): ~1 \le T, N, M \le 50~.

• Subtask 2 (50% số test): Không có ràng buộc gì thêm.