题目描述

​ 小林在社区大学上计算机课，她最近对于进制数非常感兴趣。 回想一下，一个数被写成B进制，那么这个数从右到左每位表示1，B^1，B^2，B^3，···如此下去。例如，在十进制系统下，用每位数字分别表示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，用一个空格隔开。 对于每个测试数据，保证有唯一的答案。

样例数据

input

1

419 792

output

47 35

样例说明

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

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$