小林在社区大学上计算机课，她最近对于进制数非常感兴趣。

回想一下，一个数被写成B进制，那么这个数从右到左每位表示1，B1，B2，B3，如此下去。例如，在十进制系统下，用每位数字分别表示1，10，100，1000，…以此类推。如果数字1234被理解成十进制，那么它其实应该表示的是1（1000）+2（100）+3（10）+4（1）。如果相同的数字被理解成五进制，那么它意味着1（125）+2（25）+3（5）+4（1），转换成十进制是19。小林注意到如果进制增加，相同数字串表示的值也増大。比如，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个数字的数字串，每位数字只有0~9。不幸的是，由于小林记性很差，她现在已经忘记了n、x和y。

给两个3位数字，请帮助她找出使用过的x和y。

第1行为1个正整数k。以下k行，每行一个测试数据。

每个测试数据包含两个3位数字。第一个数字n被写成x进制，

第二个数被写成y进制。n、x和y对于每个测试数据都可能不同。

输出k行，每个测试数据输出一行，表示对应的x和y，用一个空格隔开。

对于每个测试数据，保证有唯一的答案。

【样例说明】

数是8892，写成47进制是419，写成35进制是792。

【数据规模】

对于100%的数据满足：k≤100，10≤x、y≤15000。

课课通