日本人の大好物である味噌汁を作るために、最も人気のある具材の一つである豆腐を用意しています。豆腐は白い直方体状の食品で、通常は小さく切ってから汁に入れます。

あなたは、1丁の豆腐を切り分けて、少なくとも必要な個数の同じサイズの立方体を作る計画を立てています。豆腐は、その面の平行な平面に沿って切ります。各切断はブロック全体を貫通し、通過するすべての断片を分割します。豆腐の立方体が完全に切り出されるまで、豆腐のブロックやその断片を動かしてはいけません。

図 E.1. 豆腐を切る例

必要な個数の豆腐の立方体が得られる限り、できるだけ大きな立方体を作りたいと考えています。余分な豆腐の立方体や残った断片は他の料理に使えるため、それらが残ることは気にしません。

単位長さの整数倍で表される豆腐のブロックの寸法（長さ、幅、高さ）と、必要な豆腐の立方体の個数が与えられたとき、豆腐の立方体の一辺の長さの最大値を求めてください。与えられた制約の下では答えが有理数になることが証明できるため、既約分数として表現してください。

入力

入力は1つ以上のテストケースを含みます。入力の最初の行には、テストケースの数を示す整数 $t$ ($1 \le t \le 10^4$) が含まれます。続いて $t$ 個のテストケースの説明が以下の形式で続きます。

$a$ $b$ $c$ $k$

3つの整数 $a$、$b$、$c$ は、それぞれ豆腐のブロックの長さ、幅、高さを表します。これらは $1$ 以上 $10^9$ 以下の整数です。整数 $k$ ($1 \le k \le 10^9$) は、必要な豆腐の立方体の個数を表します。

出力

各テストケースについて、1行に2つの正の整数 $p$ と $q$ をスペース区切りで出力してください。ここで、$p$ と $q$ は互いに素な整数であり、$p/q$ が豆腐の立方体の一辺の長さの最大値となります。

入出力例

入力 1

3
1 1 1
2
2 2 3
7
2 3 5
240

出力 1

1 2
1 1
1 2

入力 2

3
1000000000 999999998 999999999
1000000000
1 1 999999999
1000000000
314 1000000000 1000000000
271828

出力 2

499999999 500
999999999 1000000000
314 1