对于任意两个实数 $x$ 和 $y$，定义按位异或运算 $\oplus$ 如下：

$$x \oplus y = \lim_{n \to \infty} \frac{\lfloor 2^n x \rfloor \oplus \lfloor 2^n y \rfloor}{2^n}$$

其中等式右侧的 $\oplus$ 为整数按位异或运算。 例如，$\frac{5}{8} \oplus \frac{3}{8} = \frac{3}{4}$，$\frac{1}{3} \oplus \frac{1}{7} = \frac{4}{9}$，以及 $\frac{1}{5} \oplus \frac{1}{7} = \frac{6}{65}$。

回想一下，集合 $X \subseteq \mathbb{R}$ 的上确界（记作 $\sup X$）是大于或等于 $X$ 中所有元素的最小实数。

给定四个非负有理数 $a, b, c, d$，求 $\sup \{x \oplus y : x \in [a, b], y \in [c, d]\}$。换句话说，找出大于或等于所有来自 $[a, b]$ 的元素与来自 $[c, d]$ 的元素的异或值的最小值。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

接下来是 $T$ 个测试用例。每个测试用例的第一行包含四个整数 $a_{num}, a_{denom}, b_{num}, b_{denom}$ ($0 \le a_{num}, b_{num} \le 10^{17}, 1 \le a_{denom}, b_{denom} \le 30$)，用于描述分数 $a = \frac{a_{num}}{a_{denom}}$ 和 $b = \frac{b_{num}}{b_{denom}}$。每个测试用例的第二行以相同格式描述分数 $c$ 和 $d$。

保证 $a \le b$ 且 $c \le d$，且输入的所有分数均为既约分数（即分子和分母的最大公约数为 1）。

输出格式

输出 $T$ 行。第 $i$ 行应包含两个整数 $x_{num}$ 和 $x_{denom}$，中间用空格隔开，表示第 $i$ 个测试用例的答案 $x = \frac{x_{num}}{x_{denom}}$，要求以既约分数形式表示。可以证明答案总是一个有理数。

样例

输入 1

2
0 1 1 1
0 1 1 1
5 7 5 7
3 16 3 16

输出 1

2 1
59 112

说明

在第一个样例测试用例中，答案为 2，因为我们可以通过从第一个区间选择 1，从第二个区间选择 $1 - 2^p$（其中 $p$ 为足够大的整数），使得异或值无限接近 2，但我们既无法得到精确的 2，也无法得到任何更大的数。