题目描述

奶牛贝西在当地的学院（对她来说是“奶牛学院”）上计算机课，最近她学习了用不同进制书写数字，感到非常兴奋。

回想一下，在基数为$B$的进制中，数字位从右到左分别代表$1$、$B$、$B^2$、$B^3$等等。例如，在我们熟悉的十进制中，数字位代表个位、十位、百位、千位等等。序列1234在十进制中，实际上表示$1×1000 + 2×100 + 3×10 + 4×1$。同样的序列1234在五进制中，表示$1×125 + 2×25 + 3×5 + 4×1$，在十进制中总和为194。贝西注意到，如果基数增大，由数字序列表示的数值也会增大——例如，七进制中的1234比六进制中的1234表示的数值大。

在基数$B$中书写数字时，每个数字的范围是0到$B-1$，例如在十进制中每个数字的范围是0..9，在五进制中每个数字的范围是0..4。考虑比10大的基数是完全可能的。计算机科学家经常使用十六进制，其中字母A..F代表10..15的值。例如，十六进制中的BEEF对应于$11×4096 + 14×256 + 14×16 + 15$，在十进制中总和为48879。

贝西对使用比10大得多的基数很感兴趣。她取了一个数$N$，并用两种不同的基数$X$和$Y$（$X$和$Y$都在10..15000范围内）写下来。有趣的是，在这两种情况下，她得到的都是一个3位数字序列，每个数字都在1..9范围内。不幸的是，由于贝西记忆力差，她现在忘记了$N$、$X$和$Y$！只给你她写下的两个3位数字序列，请帮助她找出她使用的两个基数$X$和$Y$。

请注意，由于$X$和$Y$可能的大小，一个穷举搜索每个可能的$X$和$Y$值（将近15000²种可能性！）的程序将无法在时间限制内运行，因此不会获得满分。

输入格式

• 输入文件以整数$K$开始，然后包含$K$行，每行指定一个单独的测试用例。每个测试用例由两个3位数字组成。第一个是用基数$X$表示的数$N$，第二个是用基数$Y$表示的数$N$（每个测试用例的$N$、$X$和$Y$可能不同）。

输出格式

• 输出应包含$K$行，每个测试用例一行。在每行上，输出相关测试用例的两个数$X$和$Y$，用空格分隔。保证每个案例都有唯一的解决方案。

样例

样例输入

1
419 792

样例输出

47 35

数据范围

10 <= $X,Y$ <= 15000，输入的两个3位数字的每个数字均在1..9范围内