La vaca Bessie ha estado tomando clases de informática en su universidad local (o "cow-ledge", en su caso), y le ha hecho mucha ilusión aprender a escribir números en diferentes bases.

Recordemos que un número escrito en base ~B~ tiene cifras que representan ~1, B, B^2, B^3~, y así de derecha a izquierda. Por ejemplo, en nuestro sistema de numeración de base 10, tenemos dígitos que representan ~1, 10, 100, 1000~ y así sucesivamente. La secuencia de dígitos ~1234~, interpretada en base 10, significa en realidad ~1*(1000) + 2*(100) + 3*(10) + 4*(1)~.

La misma secuencia de dígitos ~1234~, interpretada en base 5, significaría ~1*(125) + 2*(25) + 3*(5) + 4*(1)~, lo que equivale al número ~194~ en base 10. Bessie se da cuenta que si la base aumenta, también lo hace el número representado por una secuencia de dígitos: por ejemplo, ~1234~ en base 7 representa un número mayor que ~1234~ en base 6.

Al escribir números en base ~B~, cada dígito puede ir de ~0~ a ~B-1~, así por ejemplo en base 10 cada dígito está en el rango ~0..9~, y en base 5 cada dígito está en el rango ~0..4~. Es perfectamente posible considerar bases mayores que 10. Los informáticos suelen utilizar la base 16 ("hexadecimal"), donde las letras ~A..F~ representan dígitos de valores ~10..15~. Por ejemplo, ~BEEF~ en hexadecimal corresponde a ~11*(4096) + 14*(256) + 14*(16) + 15~, que suman el número ~48879~ en base 10.

A Bessie le intriga el concepto de utilizar bases mucho mayores que 10. Toma un número ~N~ y lo escribe en dos bases diferentes ~X~ e ~Y~, donde ~X~ e ~Y~ están en el intervalo ~10..15000~. Curiosamente, en ambos casos, obtiene una secuencia de 3 dígitos, cada uno de los cuales resulta estar en el rango ~1..9~. Por desgracia, debido a la mala memoria de Bessie, ha olvidado ~N, X~ e ~Y~. Dadas sólo las dos secuencias de 3 dígitos que escribió, por favor ayúdala a calcular las dos bases ~X~ e ~Y~ que utilizó.

Tenga en cuenta que debido al tamaño potencial de ~X~ e ~Y~, un programa que busca exhaustivamente en todos los valores posibles de ~X~ e ~Y~ (¡casi ~15000^2~ posibilidades!) no se ejecutará dentro del límite de tiempo, por lo que no no recibiría crédito completo.

Entrada

Comienza con un número entero ~K~, luego contiene ~K~ líneas cada una cada una de las cuales especifica un caso de prueba distinto. Cada caso de prueba consta de dos números de 3 dígitos. El primero es un número ~N~ escrito en base ~X~, y el ~Y~ (~N, X~ e ~Y~ pueden ser diferentes para cada caso de prueba).

Ejemplo de Entrada

1
419 792

Salida

La salida debe contener ~K~ líneas, una por cada caso de prueba. En cada línea, los dos números ~X~ e ~Y~ del caso de prueba correspondiente, separados por un espacio. Se garantiza la existencia de una soluciónpara cada caso.

Ejemplo de Salida

47 35

Explicación de la Salida: El número ~8892~, escrito en base ~47~, es ~419~. Escrito en base ~35~, es ~792~.