正整数序列定义如下：

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

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

输入格式

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

每个数据集由单行输入组成。它包含数据集编号 $K$、一个空格、分子 $p$、一个斜杠（/）以及分母 $q$。

输出格式

对于每个数据集，输出一行。包含数据集编号 $K$，后跟一个空格，再后跟满足 $F(n) = p/q$ 的 $n$ 值。输入保证 $n$ 在 32 位整数范围内。

样例

样例输入 1

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

样例输出 1

1 1
2 4
3 11
4 1431655765