Thầy giáo tiếp tục dạy An và Bình về lý thuyết số. Hôm nay, hai bạn được học về "Ước chung lớn nhất" (UCLN) và "Bội chung nhỏ nhất" (BCNN) của hai số nguyên dương.

• UCLN của hai số a và b là số nguyên dương lớn nhất mà cả a và b đều chia hết.
• BCNN của hai số a và b là số nguyên dương nhỏ nhất mà chia hết cho cả a và b.

Thầy giáo giao cho hai bạn bài tập viết một chương trình có thể tìm UCLN và BCNN của nhiều cặp số khác nhau. Bạn hãy giúp hai bạn bằng cách sử dụng thuật toán Euclid để viết hàm tìm UCLN, sau đó dùng nó để tính BCNN.

Định dạng đầu vào

Dòng đầu tiên chứa một số nguyên ~T~ (~1 \le T \le 1000~), là số lượng cặp số cần xử lý.

~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a~ và ~b~ (~1 \le a, b \le 1\,000\,000\,000~).

Định dạng đầu ra

Đối với mỗi cặp số ~a, b~, in ra UCLN và BCNN của chúng trên một dòng, cách nhau bởi một dấu cách.

Sample Input

2
6 8
10 15

Sample Output

2 24
5 30