問題文

任意の正の有理数 $u$ について、$u = \dfrac{p}{q}$ となる互いに素な正整数の組 $(p,q)$ が 唯一存在するので、このような $(p,q)$ を $(\ p(u),q(u)\ )$ と表します。

簡単な問題文

頂点集合を $V$, 辺集合を $E$ とするグラフ $G=(V,E)$ を次のように定めます。

$V=\lbrace u\in \mathbb{Q}_{\gt 0}\ |\ 1\le p(u)\lt q(u) \rbrace$ $\qquad$ $E=\lbrace (u, \dfrac{p(u)+1}{q(u)+1})\ |\ u\in V \rbrace$

$Q$ 個のクエリが与えられます。 $i$ 番目のクエリでは $u_i,v_i\in V$ が与えられます。 上記の根付き木における頂点 $u_i,v_i$ の最小共通祖先を求めてください。

厳密な問題文

頂点集合を $V$, 辺集合を $E$ とするグラフ $G=(V,E)$ を次のように定めます。

$V=\lbrace u\in \mathbb{Q}_{\gt 0}\ |\ 1\le p(u)\lt q(u)\le 10^{10^{100}} \rbrace$ $\qquad$ $E=\lbrace (u, \dfrac{p(u)+1}{q(u)+1})\ |\ u\in V,\ \dfrac{p(u)+1}{q(u)+1}\in V \rbrace$

$i$ 番目のクエリでは $T$ の $2$ つの頂点 $u_i,v_i$ が $p(u_i),q(u_i),p(v_i),q(v_i)$ によって与えられます。 $T$ における頂点 $u_i,v_i$ の最小共通祖先を頂点 $l_i$ とするとき、 $p(l_i),q(l_i)$ を求めてください。

制約

入力

$Q$
$p(u_1)$ $q(u_1)$ $p(v_1)$ $q(v_1)$
$p(u_2)$ $q(u_2)$ $p(v_2)$ $q(v_2)$
          $\vdots$
$p(u_Q)$ $q(u_Q)$ $p(v_Q)$ $q(v_Q)$

出力

$i$ 番目のクエリの答えが頂点 $l_i$ であるとき、 $p(l_i), q(l_i)$ を空白区切りで出力してください。 クエリ毎に改行してください。

サンプル

3
1 2 1 3
2 5 4 7
314159265 358979323 271828182 845904523

1 2
2 3
8 9