一个由正有理数标记的无限满二叉树定义如下：

• 根节点的标记为 $1/1$。
• 标记为 $p/q$ 的节点的左孩子标记为 $p/(p+q)$。
• 标记为 $p/q$ 的节点的右孩子标记为 $(p+q)/q$。

该树的顶部如下图所示：

通过对树进行层序遍历（广度优先搜索，由浅色虚线指示）可以定义一个有理数序列。因此：

$F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F(5) = 3/2, F(6) = 2/3, \dots$

编写一个程序，输入一个最简分数形式的有理数 $p/q$，并找出序列中的下一个有理数。也就是说，如果 $F(n) = p/q$，则结果为 $F(n+1)$。

输入格式

输入的第一行包含一个整数 $P$ ($1 \le P \le 1000$)，表示随后数据集的数量。每个数据集应被独立处理。

每个数据集由单行输入组成。它包含数据集编号 $K$，后跟一个空格，然后是分数的分子 $p$，紧接着是一个正斜杠（/），最后是分数的分母 $q$。$p$ 和 $q$ 互质，且 $0 < p, q \le 2147483647$。

输出格式

对于每个数据集，输出一行。它包含数据集编号 $K$，后跟一个空格，然后是分数的分子，紧接着是一个正斜杠（/），最后是分数的分母。输入的选取保证分子和分母都不会超过 32 位整数的范围。

样例

输入格式 1

5
1 1/1
2 1/3
3 5/2
4 2178309/1346269
5 1/10000000

输出格式 1

1 1/2
2 3/2
3 2/5
4 1346269/1860498
5 10000000/9999999