두 진법 찾기

소 베시는 대학에서 컴퓨터 수업을 듣다가 수를 여러 진법으로 적는 방법을 배웠다.

$B$진법으로 적은 수는 오른쪽부터 차례로 $1$, $B$, $B^2$, $B^3$ 자리를 나타낸다. 익숙한 십진법에서 각 자리가 $1$, $10$, $100$, $1000$을 뜻하는 것과 같다. 숫자 나열 $1234$를 십진법으로 읽으면 $1(1000) + 2(100) + 3(10) + 4(1)$이고, 같은 나열을 $5$진법으로 읽으면 $1(125) + 2(25) + 3(5) + 4(1)$이어서 십진법의 $194$가 된다. 진법이 커지면 같은 숫자 나열이 나타내는 수도 커진다. 예를 들어 $7$진법의 $1234$는 $6$진법의 $1234$보다 크다.

$B$진법에서 각 자리의 숫자는 $0$부터 $B-1$까지다. 십진법이면 $0$부터 $9$까지, $5$진법이면 $0$부터 $4$까지다. $10$보다 큰 진법도 쓸 수 있다. 컴퓨터 분야에서 자주 쓰는 $16$진법은 문자 A부터 F까지로 $10$부터 $15$까지의 값을 나타낸다. $16$진법의 BEEF는 $11(4096) + 14(256) + 14(16) + 15$이고, 십진법으로는 $48879$다.

베시는 $10$보다 훨씬 큰 진법에 흥미를 느꼈다. 어떤 수 $N$을 서로 다른 두 진법 $X$와 $Y$로 적었고, $X$와 $Y$는 모두 $10$ 이상 $15000$ 이하다. 두 경우 모두 결과는 세 자리 숫자 나열이었고, 각 자리의 숫자는 $1$부터 $9$까지였다. 그런데 베시는 $N$과 $X$, $Y$를 모두 잊어버렸다. 적어 둔 두 개의 세 자리 나열만 보고 베시가 사용한 두 진법 $X$와 $Y$를 알아내라.

$X$와 $Y$가 가질 수 있는 값이 많아서, 가능한 $(X, Y)$ 쌍을 전부 시도하는 풀이는 약 $15000^2$가지를 확인하므로 제한 시간 안에 끝나지 않는다.

첫 줄에 정수 $K$가 주어진다. 다음 $K$개의 줄에는 각각 테스트 케이스가 하나씩 주어진다. 각 테스트 케이스는 세 자리 수 두 개로 이루어진다. 첫 번째 수는 $N$을 $X$진법으로 적은 것이고, 두 번째 수는 같은 $N$을 $Y$진법으로 적은 것이다. $N$과 $X$, $Y$는 테스트 케이스마다 다를 수 있다.

$K$개의 줄을 출력한다. 각 줄에 해당 테스트 케이스의 $X$와 $Y$를 공백 하나로 구분해 출력한다. 각 테스트 케이스의 답은 하나뿐임이 보장된다.

$8892$를 $47$진법으로 적으면 $419$이고, $35$진법으로 적으면 $792$다.