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

• 根节点的标记为 $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$

编写一个程序来计算该序列的第 $n$ 个元素 $F(n)$。这个问题听起来耳熟吗？确实应该如此！我们在 2014 年和 2015 年的大纽约地区赛中出现过该问题的变体。

输入格式

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

每个数据集由单行输入组成。它包含数据集编号 $K$ 以及需要计算的序列索引 $N$ ($1 \le N \le 2147483647$)。

输出格式

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

样例

输入 1

4
1 1
2 4
3 11
4 1431655765

输出 1

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