Cô bò Bessie đang theo học các lớp tin học tại trường cao đẳng địa phương (hay "cow-ledge" trong trường hợp của cô), và gần đây cô rất hào hứng khi học được cách viết các số trong những hệ cơ số khác nhau.

Hãy nhớ rằng một số viết trong hệ cơ số \(B\) có các hàng chữ số lần lượt biểu diễn \(1\), \(B\), \(B^2\), \(B^3\), v.v. từ phải sang trái. Chẳng hạn, trong hệ cơ số 10 quen thuộc, các chữ số lần lượt biểu diễn hàng đơn vị, hàng chục, hàng trăm, hàng nghìn, v.v. Dãy chữ số 1234 khi được hiểu trong hệ cơ số 10 thực chất có nghĩa là \(1(1000) + 2(100) + 3(10) + 4(1)\). Cũng dãy chữ số 1234 ấy, nếu được hiểu trong hệ cơ số 5, sẽ có nghĩa là \(1(125) + 2(25) + 3(5) + 4(1)\), tổng lại bằng số 194 trong hệ cơ số 10. Bessie nhận thấy rằng khi cơ số tăng, số được biểu diễn bởi một dãy chữ số cũng tăng theo — chẳng hạn, 1234 trong hệ cơ số 7 biểu diễn một số lớn hơn 1234 trong hệ cơ số 6.

Khi viết số trong hệ cơ số \(B\), mỗi chữ số có thể nhận giá trị từ 0 đến \(B-1\). Vì vậy, chẳng hạn trong hệ cơ số 10, mỗi chữ số nằm trong đoạn \(0\ldots9\), còn trong hệ cơ số 5, mỗi chữ số nằm trong đoạn \(0\ldots4\). Hoàn toàn có thể xét các cơ số lớn hơn 10. Các nhà khoa học máy tính thường dùng hệ cơ số 16 ("thập lục phân"), trong đó các chữ cái A đến F biểu diễn các chữ số có giá trị từ 10 đến 15. Chẳng hạn, BEEF trong hệ thập lục phân tương ứng với \(11(4096) + 14(256) + 14(16) + 15\), tổng lại bằng số 48879 trong hệ cơ số 10.

Bessie bị cuốn hút bởi ý tưởng sử dụng những cơ số lớn hơn 10 rất nhiều. Cô lấy một số \(N\) và viết nó trong hai hệ cơ số khác nhau \(X\) và \(Y\), trong đó cả \(X\) lẫn \(Y\) đều thuộc đoạn \(10\ldots15\,000\). Điều thú vị là trong cả hai trường hợp, cô đều nhận được một dãy gồm 3 chữ số, và mỗi chữ số tình cờ chỉ nằm trong đoạn \(1\ldots9\). Đáng tiếc, do trí nhớ kém, giờ đây Bessie đã quên mất \(N\), \(X\) và \(Y\)! Chỉ với hai dãy 3 chữ số mà cô đã viết ra, hãy giúp cô tìm lại hai cơ số \(X\) và \(Y\) đã sử dụng.

Lưu ý rằng do \(X\) và \(Y\) có thể rất lớn, một chương trình vét cạn mọi giá trị có thể của \(X\) và \(Y\) (gần \(15\,000^2\) khả năng!) sẽ không chạy kịp giới hạn thời gian, vì vậy sẽ không nhận được trọn vẹn số điểm.

Dữ liệu vào

Dữ liệu vào bắt đầu bằng một số nguyên \(K\), sau đó là \(K\) dòng, mỗi dòng mô tả một bộ test riêng biệt. Mỗi bộ test gồm hai số có 3 chữ số. Số đầu tiên là số \(N\) được viết trong hệ cơ số \(X\), còn số thứ hai là \(N\) được viết trong hệ cơ số \(Y\) (\(N\), \(X\) và \(Y\) có thể khác nhau giữa các bộ test).

Dữ liệu ra

Kết quả phải gồm \(K\) dòng, mỗi dòng ứng với một bộ test. Trên mỗi dòng, in hai số \(X\) và \(Y\) của bộ test tương ứng, cách nhau bởi một dấu cách. Dữ liệu bảo đảm mỗi bộ test có đúng một nghiệm.

Ví dụ

1
419 792

47 35

Nguồn

USACO 2015 January Contest, Bronze - It's All About the Base: https://usaco.org/index.php?page=viewproblem2&cpid=509

Tác giả: Brian Dean, 2015.