Euklid

Σπάνια αναφέρεται ότι η γιαγιά του Ευκλείδη ήταν από τη Vrsi της Κροατίας. Από εκεί κατάγεται ο λιγότερο γνωστός (αλλά εξίσου ταλαντούχος στα νιάτα του) ξάδερφος του Ευκλείδη, Edicul ~^*~.

Έτυχε, λοιπόν, μια μέρα που έπαιζαν «εφεύρεση αλγόριθμου». Ο Edicul γράφει δύο θετικούς ακέραιους αριθμούς στην άμμο. Στη συνέχεια κάνει το εξής: ενώ κανένας αριθμός στην άμμο δεν είναι 1, τους σημειώνει ως ~(a,\;b)~ έτσι ώστε ~a \ge b~. Μετά σβήνονται οι αριθμοί και γράφει ~([\frac{a}{b}],\;b)~ στην άμμο και επαναλαμβάνει τη διαδικασία. Όταν ένας από τους δύο αριθμούς γίνεται 1, ο άλλος είναι τα αποτελέσματα του αλγορίθμου του.

Τυπικά, εάν τα ~a~ και ~b~ είναι θετικοί ακέραιοι, το αποτέλεσμα ~R(a,\;b)~ του αλγορίθμου του Edicul είναι:

$$\displaystyle R(a, b) = \begin{cases} R(a, b), & \text{αν } & a \leq 4 \\ R([~\frac{a}{b}~], b) & \text{αν } & a \geq b > 1 \\ a & \text{αν } & a \geq b = 1. \end{cases}$$

Ο Ευκλείδης σκέφτεται λίγο και λέει: "Edicul, έχω καλύτερη ιδέα~\ldots~" και η εξέλιξη φαίνεται από την ιστορία. Δυστυχώς, ο Edicul δεν έγινε ποτέ διάσημος για την ιδέα του στη θεωρία αριθμών. Αυτή η θλιβερή ιστορία εμπνέει το ακόλουθο πρόβλημα: Δεδομένων των θετικών ακεραίων ~g~ και ~h~, βρείτε θετικούς ακέραιους αριθμούς a και b τέτοιους ώστε ο μέγιστος κοινός διαιρέτης τους να είναι ~g~ και το αποτέλεσμα του αλγορίθμου του Edicul ~R(a,\;b)~ να είναι ~h~.

Η πρώτη γραμμή περιέχει έναν μόνο ακέραιο ~t\;(1 \le t \le 40)~ – τον αριθμό των ανεξάρτητων περιπτώσεων δοκιμής. Κάθε μία από τις ακόλουθες ~t~ γραμμές περιέχει δύο θετικούς ακέραιους ~g_i~ και ~h_i\;(h_i \ge 2)~.

Έξοδος

Η έξοδος περιλαμβάνει ~t~ γραμμές. Για την ~i~-οστή δοκιμαστική περίπτωση, τυπώνετε τους θετικούς ακέραιους αριθμούς ~a_i~ και ~b_i~, έτσι ώστε ~gcd(a_i,\;b_i) = g_i~ και ~R(a_i,\;b_i) = h_i~.

Οι αριθμοί στην έξοδο δεν πρέπει να είναι μεγαλύτεροι από ~10^{18}~. Μπορεί να αποδειχθεί ότι, για τους δεδομένους περιορισμούς, υπάρχει πάντα μια λύση.

Εάν υπάρχουν πολλές λύσεις για κάποια δοκιμαστική περίπτωση, τυπώστε οποιαδήποτε από αυτές.

Βαθμολογία

Σε όλα τα υποπροβλήμαρα, ~1 \le g \le 200\,000~ και ~2 \le h \le 200\,000~.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	4	~g = h~
2	8	~h = 2~
3	8	~g = h^2~
4	15	~g, h \le 20~
5	40	~g, h \le 2\,000~
6	35	Κανένας επιπλέον περιορισμός.

~^*~ Αυτό δημιουργεί ένα λογοπαίγνιο στα Κροατικά. Η μετάφραση είναι λίγο "ήπια", συγγνώμη για αυτό.

Παραδείγματα

input

1
1 4

output

99 23

Επεξήγηση του 1ου παραδείγματος:

Οι ακέραιοι 99 και 23 είναι συμπρώτοι, δηλαδή ο μεγαλύτερος κοινός διαιρέτης τους είναι 1. Έχουμε ~[\frac{99}{23}] = 4~, έτσι το ~R(99,\;23) = R(4,\;23) = R(23,\;4)~. Τότε ~[\frac{23}{4}] = 5~, άρα ~R(23,\;4) = R(5,\;4) = R(1,\;4) = R(4,\;1) = 4~.

input

1
1 4

output

99 23

Επεξήγηση του 2ου παραδείγματος:

Για την πρώτη περίπτωση, ~gcd(9,\;39) = 3~ και ~R(9,\;39) = 2~.
Για την περίπτωση δοκιμής, ~gcd(5,\;5) = 5~ και ~R(5,\;5) = 5~.