Với mỗi bộ ba số nguyên ~a, b, c~, hãy tìm số nguyên dương ~x~ nhỏ nhất sao cho đồng thời ba điều kiện sau đều đúng:

• tích ~a \times x~ là bội của ~b~;
• tích ~b \times x~ là bội của ~c~;
• tích ~c \times x~ là bội của ~a~.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~T~ (~1 \le T \le 10^5~), là số bộ ba cần xử lý.
• Trong ~T~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~a, b, c~ (~1 \le a, b, c \le 10^6~) của bộ ba thứ ~i~.

Kết quả

In ra ~T~ dòng, dòng thứ ~i~ là giá trị ~x~ nhỏ nhất tìm được cho bộ ba thứ ~i~.

Ví dụ

MINX.INP

3
4 6 10
12 34 56
999961 999979 999983

MINX.OUT

30
1428
999923001838986077

Giới hạn

• Subtask 1 (40% số điểm): ~T \le 10~, ~a, b, c \le 100~.
• Subtask 2 (30% số điểm): ~T \le 10~, ~a, b, c \le 1000~.
• Subtask 3 (30% số điểm): không có ràng buộc thêm.