Bessie has been learning about writing numbers in different bases. A number written in base B has digit places representing 1, B, B^2, B^3, and so on. For example, 1234 in base 5 means 1(125) + 2(25) + 3(5) + 4(1) = 194 in base 10.

Bessie takes a number N and writes it down in two different bases X and Y, where both X and Y are in the range 10..15,000. Interestingly, in both cases, she gets a sequence of 3 digits, each of which happens to be only in the range 1..9. Unfortunately she has forgotten N, X, and Y! Given just the two 3-digit sequences she wrote down, please help her figure out the two bases X and Y that she used.

Note: a program that searches exhaustively over every possible value of X and Y (nearly 15,000^2 possibilities) will not run within the time limit.

The input starts with an integer K, then K lines each specifying a test case. Each test case consists of two 3-digit numbers: a number N written in base X, and N written in base Y.

K lines, one per test case. On each, output the two bases X and Y separated by a space. A unique solution for each case is guaranteed.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > January > Bronze