분수 XOR 최대화

실수 $x$와 $y$에 대한 비트 XOR 연산 $\oplus$를 다음과 같이 정의한다. $x \oplus y = \lim_{n \to \infty}{\frac{\lfloor2^nx\rfloor \oplus \lfloor 2^ny\rfloor}{2^n}}$ 오른쪽 식의 $\oplus$는 정수 비트 XOR 연산이다. 예를 들어 $\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]$의 원소로 만든 모든 XOR 값보다 크거나 같은 가장 작은 값을 구하라.

첫 줄에 테스트 케이스 수 $T$($1 \le T \le 100$)가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 $a = \frac{a_{num}}{a_{denom}}$과 $b = \frac{b_{num}}{b_{denom}}$을 나타내는 정수 $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$)이 주어진다. 둘째 줄에는 같은 형식으로 $c$와 $d$가 주어진다. 모든 분수는 기약분수이며, $a \le b$와 $c \le d$가 보장된다.

$T$줄에 걸쳐 각 테스트 케이스의 답 $x = \frac{x_{num}}{x_{denom}}$의 분자와 분모를 한 칸 띄워 출력한다. 답은 기약분수로 나타낸다.

첫 번째 테스트 케이스의 답은 $2$이다. 첫 번째 구간에서 $1$을, 두 번째 구간에서 $1 - 2^p$를 고르면 충분히 큰 정수 $p$에 대해 XOR 값을 $2$에 한없이 가깝게 만들 수 있다. 그러나 $2$ 이상의 값은 어떤 경우에도 만들 수 없다.