Cho hai số nguyên dương x, y, tìm số nguyên dương z nhỏ nhất để x*z chia hết cho y.

Dữ liệu vào: Đọc từ file văn bản LMUL.INP:

• Dòng một chứa số nguyên dương \(T \leq 10 ^ 5\) là số bộ test;
• T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(x, y \leq 10 ^{18}\)

Kết quả: Ghi ra file văn bản LMUL.OUT:

• Gồm T dòng tương ứng với mỗi test, ghi ra một số nguyên dương z là kết quả tìm được.

Ràng buộc:

• Subtask 1: Có 25% số test ứng với 25% số điểm có T <= 100 và x, y <= 100
• Subtask 2: Có 25% số test khác ứng với 25% số điểm có T < 100 và \(x, y <= 10 ^ 9\)
• Subtask 3: Có 50% số test còn lại không có ràng buộc bổ sung.

2
5 10
4 6

2
3