#214782. [ICPC 2025 Yokohama R] Cutting Tofu

You are preparing miso soup, a favorite among Japanese people, with one of the most popular ingredients, tofu. Tofu is a white cuboid-shaped food that is usually cut into smaller pieces and then put into the soup.

You plan to chop a single block of tofu to make at least a required number of cubes of the same size. You cut the tofu along planes parallel to the faces of the tofu block. Each cut goes all the way through the block, dividing all the pieces it passes through. You should not move the tofu block nor its fragments until tofu cubes are completely cut out.

:::align{center}

Figure E.1. An example of cutting the tofu :::

As long as the required number of tofu cubes can be obtained, you want to make cubes as large as possible. You don't mind leaving excess tofu cubes or leftover fragments, as they can be used for other dishes.

Given the dimensions of the block of tofu (its length, width, and height) in integer multiples of unit length, and the required number of tofu cubes, your task is to find the maximum possible side length of the tofu cubes. Since it can be proven that the answer is a rational number under the given constraints, it should be represented as a reduced fraction.

The input contains one or more test cases. The first line of the input contains an integer (), which is the number of test cases. The descriptions of the test cases follow, each in the following format.

The three integers , , and represent the length, width, and height of the block of tofu, respectively. They are between 1 and , inclusive. The integer () represents the required number of tofu cubes.

For each test case, output two positive integers and in a line, separated by a single space. Here, and are mutually prime integers, meaning that is the maximum possible side length of the tofu cubes.

样例输入 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