문제

민준이는 최근 컴퓨터 개론 수업에서 서로 다른 진법으로 수를 표현하는 방법을 배웠다.

진법 $B$로 작성된 수는 오른쪽에서 왼쪽으로 각각 $1, B, B^2, B^3, \dots$를 나타내는 자릿수를 가진다. 예를 들어, 우리가 익숙한 $10$진법 체계에서는 $1, 10, 100, 1000, \dots$를 나타내는 자릿수가 있다. $10$진법으로 쓴 숫자 배열 $1234$는 $1(1000) + 2(100) + 3(10) + 4(1)$을 의미한다. 같은 숫자 배열 $1234$를 $5$진법으로 해석하면 $1(125) + 2(25) + 3(5) + 4(1)$이 되어, $10$진법으로는 $194$가 된다. 민준이는 진법이 커질수록 같은 숫자 배열이 나타내는 값도 커진다는 점을 발견했다. 예를 들어, $7$진법의 $1234$는 $6$진법의 $1234$보다 더 큰 수를 나타낸킨다.

$B$진법으로 수를 쓸 때, 각 자릿수는 $0$부터 $B-1$까지의 값을 가질 수 있다. 따라서 $10$진법의 각 자릿수는 $0$에서 $9$까지, $5$진법은 $0$에서 $4$까지의 범위를 갖는다. $10$보다 큰 진법을 사용하는 것도 가능하다. 컴퓨터 과학에서는 $16$진법을 자주 사용하며, 여기서는 알파벳 A부터 F까지를 $10$부터 $15$까지의 자릿값으로 사용한다. 예를 들어, $16$진법의 BEEF는 $11(4096) + 14(256) + 14(16) + 15$에 해당하며, 이를 $10$진법으로 환산하면 $48\,879$가 된다.

민준이는 $10$보다 훨씬 큰 진법을 사용하는 것에 흥미를 느꼈다. 민준이는 어떤 수 $N$을 가져와 두 개의 서로 다른 진법 $X$와 $Y$로 적었다. 여기서 $X$와 $Y$는 모두 $10$에서 $15\,000$ 사이의 정수이다. 흥미롭게도, 두 경우 모두 결과는 $3$자리의 숫자 배열이 되었으며, 각 자릿수는 우연히도 $1$에서 $9$ 사이의 숫자였다. 하지만 민준이는 건망증 때문에 $N, X, Y$를 모두 잊어버리고 말았다! 민준이가 적어둔 두 개의 $3$자리 숫자 배열이 주어질 때, 사용된 두 진법 $X$와 $Y$를 알아내는 프로그램을 작성하시오.

참고로 $X$와 $Y$의 범위가 크기 때문에, 가능한 모든 $X$와 $Y$의 조합을 전부 확인하는 방식($15\,000^2$에 가까운 경우의 수)은 시간 제한 내에 통과하지 못할 수 있음에 유의하라.

입력

첫째 줄에 테스트 케이스의 개수 $K$가 주어진다. 이어서 $K$개의 줄에 걸쳐 각 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 개의 $3$자리 숫자로 구성된다. 첫 번째 숫자는 수 $N$을 $X$진법으로 쓴 것이고, 두 번째 숫자는 같은 수 $N$을 $Y$진법으로 쓴 것이다. ($10 \le X, Y \le 15\,000$)

출력

각 테스트 케이스마다 한 줄에 하나씩, 사용된 두 진법 $X$와 $Y$를 공백으로 구분하여 출력한다. 각 케이스마다 정답은 유일하게 존재함이 보장된다.

예제 입력 1

1
419 792

예제 출력 1

47 35