Беси пошла компьютерные курсы и восхищена темой "Системы счисления". Напомним, что число, записанное в системе счисления b имеет цифровые места, представляющие 1, b, b2, b3, ... справа налево. Например, для 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..15000. Интересно, что в обоих случаях она получает последовательность из 3 цифр, каждое из которых в диапазоне 1..9.

К сожалению, из-за плохой памяти Беси забыла n x y. Пожалуйста, помогите ей по двум 3-цифровым последовательностям, которые она выписала, определить системы счисления x и y, которые она использовала. Заметим, что программа, которая просто будет перебирать все возможные сочетания x и y (примерно 150002 вариантов) не пройдёт по времени, и не получит полный балл.

Входные данные

Начинается с целого числа k, затем оно содержит k строк, каждая из которых отдельный тест. Каждый тест состоит из двух 3-значных чисел. Первое - число n, записанное в системе счисления с основанием x, второе - число n, записанное в системе счисления с основанием y. n x y могут различаться для каждого теста.

Выходные данные

Выведите k строк, по одной для каждого теста. На каждой строке выведите два числа x и y для соответствующего теста. Гарантируется существование и единственность решения.

Пример

Число 8892, записанное в системе счисления с основанием 47 есть 419, и это же число, записанное в системе счисления с основанием 35 есть 792.