你正在准备日本人最喜爱的味噌汤，其中最受欢迎的食材之一就是豆腐。豆腐是一种白色的长方体食物，通常被切成小块后放入汤中。

你计划将一块豆腐切成至少所需数量的相同大小的立方体。你沿着平行于豆腐块表面的平面进行切割。每一次切割都会贯穿整个豆腐块，将它所经过的所有部分一分为二。在豆腐块被完全切成小立方体之前，你不应移动豆腐块或其碎片。

图 E.1. 切割豆腐的示例

只要能获得所需数量的豆腐立方体，你希望立方体尽可能大。你不介意留下多余的豆腐立方体或剩余的碎片，因为它们可以用于其他菜肴。

给定豆腐块的尺寸（长、宽、高，均为单位长度的整数倍）以及所需的豆腐立方体数量，你的任务是找到豆腐立方体可能的最大边长。由于可以证明在给定的约束条件下答案是一个有理数，因此它应该表示为一个最简分数。

输入格式

输入包含一个或多个测试用例。输入的第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。接下来是 $t$ 个测试用例的描述，每个用例的格式如下：

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

三个整数 $a$、$b$ 和 $c$ 分别表示豆腐块的长、宽和高。它们的值在 $1$ 到 $10^9$ 之间（含边界）。整数 $k$ ($1 \le k \le 10^9$) 表示所需的豆腐立方体数量。

输出格式

对于每个测试用例，输出两个正整数 $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