Người ta hiếm khi đề cập rằng bà của Euclid đến từ Vrsi ở Croatia. Đó là nơi ở của người anh họ - Edicul ít được biết đến hơn (nhưng không kém phần tài năng) của Euclid.

Một ngày nọ, họ đang chơi trò "phát minh ra một thuật toán". Edicul viết hai số nguyên dương trên cát. Sau đó, anh ta làm như sau: trong khi không có số nào trên cát là ~1~, anh ta đánh dấu chúng là ~(a, b)~ sao cho ~a ≥ b~. Sau đó, các con số bị xóa và anh ấy viết ~(\lfloor \frac a b \rfloor~, ~b)~ trên cát, và lặp lại quá trình. Khi một trong hai số trở thành ~1~ thì số còn lại là kết quả của thuật toán của anh ta.

Về mặt hình thức, nếu ~a~ và ~b~ là các số nguyên dương, kết quả ~R(a, b)~ của thuật toán Edicul là:

$$ R(a, b) = \begin{cases} R(b,a) & \text{nếu } a < b \\ R(\lfloor \frac a b \rfloor, b) & \text{nếu } a \geq b > 1 \\ a & \text{nếu } a \geq b = 1 \end{cases} $$

Euclid suy nghĩ một lúc và nói: "Edicul, tôi có một ý tưởng hay hơn ...", và phần còn lại là lịch sử. Thật không may, Edicul chưa bao giờ trở nên nổi tiếng vì ý tưởng của mình trong lý thuyết số. Câu chuyện buồn này đã dẫn đến câu hỏi sau:

Cho các số nguyên dương ~g~ và ~h~, hãy tìm các số nguyên dương ~a~ và ~b~ sao cho ước chung lớn nhất của chúng là ~g~ và kết quả của thuật toán Edicul ~R(a, b)~ là ~h~.

Input

Dòng đầu chứa số nguyên ~T~ (~1 \leq T \leq 40~) là số bộ test

~T~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên dương ~g_i~, ~h_i~ ~(h_i \geq 2)~

Output

Gồm ~T~ dòng. Dòng thứ ~i~ chứa ~2~ số nguyên dương ~a_i~ và ~b_i~ sao cho ~gcd~(~a_i~, ~b_i~)= ~g_i~ và ~R(a_i, b_i)~= ~h_i~

Kết quả không vượt quá ~10^{18}~ và luôn tồn tại

Nếu có nhiều đáp án, in ra đáp án bất kì

Sample Input 1

1
1 4

Sample Output 1

99 23

Sample Input 2

2
3 2
5 5

Sample Output 2

9 39
5 5

Giải thích cho ví dụ 1:

~99~ và ~23~ là hai số nguyên tố cùng nhau (có ước chung lớn nhất là 1). Ta có ~[\frac{99}{23}]~ ~= 4~ vì vậy ~R(99,23) = R(4,23) = R(23,4)~. Tiếp đến ta có ~[\frac{23}{4}] = 5~ nên ~R(23,4) = R(5,4) = R(1,4) = R(4,1) = 4~

Giải thích cho ví dụ 2:

Testcase 1, ~gcd(3,39) = 3~ và ~R(3,39) = 2~

Testcase 2, ~gcd(5,5) = 5~ và ~R(5,5) = 5~

Subtask

• Có ~5~ test ~g = h~

• Có ~9~ test ~h = 2~

• Có ~9~ test ~g = h^2~

• Có ~10~ test ~g, h \leq 20~

• Có ~22~ test ~g, h \leq 2000~

• Số test còn lại không có ràng buộc gì thêm.