Уся справа в базі
Бесі пішла на комп'ютерні курси і захопилася темою "Системи числення". Нагадаємо, що число, записане в системі числення з основою b, має цифрові місця, що представляють 1, b, b^2, b^3, ... справа наліво. Наприклад, у десятковій системі ми маємо цифри, що представляють 1, 10, 100, 1000, ... Послідовність цифр 1234 в десятковій системі означає:
1(1000) + 2(100) + 3(10) + 4(1)
Така ж послідовність в п'ятірковій системі означає:
1(125) + 2(25) + 3(5) + 4(1)
І дає число 194 в десятковій системі.
Бесі помітила, що якщо основа системи числення b зростає, то зростає і число, яке вона представляє. Наприклад, 1234 в сімірковій системі представляє більше число, ніж 1234 в шістковій системі.
Коли ми записуємо число в системі числення з основою b, кожна цифра може бути в діапазоні від 0 до b - 1. Тому, наприклад, у десятковій системі цифри знаходяться в діапазоні 0..9, а в п'ятірковій системі - в діапазоні 0..4.
Можна розглядати системи числення з основою більше ніж 10. Наприклад, комп'ютерні спеціалісти часто використовують систему з основою 16, де використовуються літери A..F для позначення величин 10..15. Наприклад, BEEF в шістнадцятковій системі відповідає:
11(4096) + 14(256) + 14(16) + 15,
що в сумі дає 48879 в десятковій системі.
Бесі заінтригована концепцією використання основ більше 10. Вона бере число n і записує його в двох різних системах числення x і y, кожна з яких у діапазоні від 10 до 15000. Цікаво, що в обох випадках вона отримує послідовність з 3 цифр, кожна з яких у діапазоні від 1 до 9.
На жаль, через погану пам'ять Бесі забула n, x, і y. Будь ласка, допоможіть їй, використовуючи дві 3-цифрові послідовності, які вона записала, визначити системи числення x і y, які вона використовувала. Зазначимо, що програма, яка просто перебирає всі можливі комбінації x і y (приблизно 15000^2 варіантів), не пройде за часом і не отримає повний бал.
Вхідні дані
Починається з цілого числа k, далі йдуть k рядків, кожен з яких є окремим тестом. Кожен тест складається з двох 3-значних чисел. Перше - число n, записане в системі числення з основою x, друге - число n, записане в системі числення з основою y. n, x, і y можуть відрізнятися для кожного тесту.
Вихідні дані
Виведіть k рядків, по одному для кожного тесту. На кожному рядку виведіть два числа x і y для відповідного тесту. Гарантовано існування і єдиність розв'язку.
Приклад
Число 8892, записане в системі числення з основою 47, є 419, і це ж число, записане в системі числення з основою 35, є 792.