Беси пошла компьютерные курсы и восхищена темой «Системы
счисления». Напомним, что число, записанное в системе счисления
B имеет цифровые места, представляющие 1, B, B^2, B^3 … справа
налево. Например, для 10-ой системы счисления мы имеем цифры,
представляющие 1, 10, 100, 1000, … Последовательность цифр 1234
в 10-й системе означает
1(1000) + 2(100) + 3(10) + 4(1).
Та же последовательность в 5-ой системе означает
1(125) + 2(25) + 3(5) + 4(1)
И даёт число 194 в 10-й системе.
Беси заметила, что если основание системы счисления B возрастает,
возрастает и число, им представляемое. Например, 1234 в 7-ой системе
счисления представляет большее число, чем 1234 в 6-ой системе
счисления.
Когда мы записываем число в системе счисления с основанием B,
каждая цифра может быт в диапазоне от 0 до B-1. Поэтому, например,
в 10-й систем счисления, цифры находятся в диапазоне 0..9,
а в 5-ой систем счисления, цифры находятся в диапазоне 0..4.
Можно рассматривать системы счисления с основанием больше чем 10.
Например, компьютерные специалисты часто используют в качестве
основания системы счисления основание 16, и используют буквы A..F
для обозначения величин 10..15. Например, BEEF в 16-ой системе соответствует
11(4096) +14(256) + 14(16) + 15,
что после сложения даёт 48879 в 10-ой системе счисления.
Беси заинтригована концепцией использования оснований больше 10.
Она берёт число N и выписывает его в двух различных системах счисления X и Y,
каждое из которых в диапазоне 10..15,000. Интересно, что в обоих случаях
она получает последовательность из 3 цифр, каждое из которых в диапазоне 1..9.
К сожалению, из-за плохой памяти Беси забыла N X Y. Пожалуйста, помогите
ей по двум 3-цифровым последовательностям, которые она выписала,
определить системы счисления X и Y, которые она использовала.
Заметим, что программа, которая просто будет перебирать все возможные
сочетания X и Y (примерно 15,000^2 вариантов) не пройдёт по времени,
и не получит полный балл.
Формат входных данных
Входной файл начинается с целого числа K, затем оно содержит K строк,
каждая из которых отдельный тест. Каждый тест состоит из двух
3-значных чисел. Первое - число N, записанное в системе счисления с
основанием X, второе - число N, записанное в системе счисления с
основанием Y. N X Y могут различаться для каждого теста.
Формат выходных данных
Ваш вывод должен содержать K строк, по одной для каждого теста.
На каждой строке выведите два числа X и Y для соответствующего теста,
разделённые одиночными пробелами. Гарантируется существование и
единственность решения.
Примечание
Число 8892, записанное в системе счисления с основанием 47 есть 419,
и это же число, записанное в системе счисления с основанием 35 есть 792.