该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

牛 Petr 正在当地的大学（或者说，牛大学）里上计算机课，并且最近她兴奋于学会了用不同进制写数字。

回忆一下，一个 $B$ 进制数字从低位到高位的位权为 $1, B, B^2, B^3, \dots$ 。例如，在我们最熟悉的 $10$ 进制技术系统中，我们有位权 $1, 10, 100, 1000, \dots$ 。十进制表示下的数字 $1234$ ，实际上是 $1(1000) + 2(100) + 3(10) + 4(1)$ ，而 $5$ 进制表示下的数字 $1234$ ，实际上是 $1(125) + 2(25) + 3(5) + 4(1)$ ，转换到十进制后就是数字 $194$ 。 Petr 注意到，对于相同的数字，如果基数 $B$ 增加，那么所表示的数值也会增加。例如 $7$ 进制表示下的 $1234$ 的数值就比 $6$ 进制表示下的 $1234$ 要大。

$B$ 进制下，每一位的范围在 $0$ 到 $B - 1$ ，比方说， $10$ 进制下每位的范围是 $0 .. 9$ ， $5$ 进制下每位的范围是 $0 .. 4$ 。计算机科学家通常使用 $16$ 进制，此时 $A .. F$ 用来表示 $10 .. 15$ 。例如， $16$ 进制下 $BEEF$ 表示 $11(4096) + 14(256) + 14(16) + 15$ ，转化成 $10$ 进制就是 $48879$ 。

基数可以大于 $10$ 这一概念引起了 Petr 的兴趣。她选择了一个数字 $N$ ，并将它以 $X$ 进制和 $Y$ 进制写下来（$10 \le X, Y \le 15000$ ）。有趣的是，在两种表示方法下，她都得到了一个 $3$ 位数，每一位都在范围 $1 .. 9$ 当中。不幸的是，由于 Petr 的记性很差，她忘记了 $N$ 、 $X$ 、 $Y$ ！给出 Petr 写出的两个三位数，请你帮她求出她所选用的两个不同进制的基数 $X$ 和 $Y$ 。

注意到， $X$ 、 $Y$ 可能很大，当你实现的算法是枚举所有可能的 $X$ 、 $Y$ 值时（有 $15000^2$ 种可能！），你的程序将会运行超时，不会拿到本题满分。

输入格式

输入的第一行包含 $K(K \le 100)$ ，表示有 $K$ 组数据。每组数据包括两个三位数。第一个数是 $X$ 进制表示下的 $N$ ，而第二个数是 $Y$ 进制表示下的 $N$ （对于每组数据， $N$、 $X$ 、 $Y$ 都有可能是不同的）。

输出格式

输出 $K$ 行，每行输出对应数据组下的 $X$ 、 $Y$ ，用空格分隔。保证每组数据的答案都是唯一的。

1
419 792

47 35

提示

样例解释

$8892$ 在 $47$ 进制表示下是 $419$ ，而在 $35$ 进制表示下是 $792$ 。