Martians have discovered the answer to life, the universe, and everything. No, not 42. Wifi trees!
Martian lungs are adapted to survive without Oxygen for a looong time, but that time is about to end.
The Martians have managed to plant n Wifi trees, each additional tree supplying them with x Mbps of Wifi. However, each Martian requires one Oxygen tree in order to survive.
The government does not want to spend money on planting new trees, but it can convert some Wifi trees to Oxygen trees. Being utilitarian by nature, it wants to maximise total happiness.
Each Martian will have 1 happiness for each Mbps of Wifi he gets. However, dead Martians cannot be happy. The total happiness is the sum of happiness of each of the Martians.
Formally, happiness of some Martian i is defined as follows: Hi = ai·t·x.
ai is 1 if that Martian is alive, 0 otherwise. t is the number of Wifi trees.
Total happiness is therefore .
What is the minimum number of trees the government should convert to maximise total happiness?
The first line of the input contains an integer T, the number of test cases (1 ≤ T ≤ 5).
Each of the next T input represents a test case, and consists of 3 space-separated integers n, m, and x (1 ≤ n, m ≤ 109; 1 ≤ x ≤ 5), the number of Wifi trees, the number of Martians, and the additional bitrate provided by each Wifi tree, respectively.
Print T lines of output, one for each test case. On each line print two space-separated integers.
The first integer is the minimum number of Wifi trees that should be converted to Oxygen trees.
The second integer is the maximum happiness achieved.
To avoid overflows, use 'unsigned long long' or 'long long' in C++, and 'long' in Java, instead of 'int'
## Input
The first line of the input contains an integer T, the number of test cases (1 ≤ T ≤ 5).Each of the next T input represents a test case, and consists of 3 space-separated integers n, m, and x (1 ≤ n, m ≤ 109; 1 ≤ x ≤ 5), the number of Wifi trees, the number of Martians, and the additional bitrate provided by each Wifi tree, respectively.
## Output
Print T lines of output, one for each test case. On each line print two space-separated integers.The first integer is the minimum number of Wifi trees that should be converted to Oxygen trees.The second integer is the maximum happiness achieved.
[samples]
## Note
To avoid overflows, use 'unsigned long long' or 'long long' in C++, and 'long' in Java, instead of 'int'
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of Wifi trees.
Let $ m \in \mathbb{Z}^+ $ be the number of Martians.
Let $ x \in \mathbb{Z}^+ $ be the Mbps per Wifi tree.
Let $ c \in \mathbb{Z} $ be the number of Wifi trees converted to Oxygen trees ($ 0 \leq c \leq n $).
**Constraints**
1. $ 1 \leq T \leq 5 $
2. $ 1 \leq n, m \leq 10^9 $
3. $ 1 \leq x \leq 5 $
**Objective**
For each test case, find the minimum $ c \in \{0, 1, \dots, n\} $ such that total happiness is maximized, where:
- Number of alive Martians: $ a = \min(m, n - c) $
- Number of Wifi trees remaining: $ t = n - c $
- Total happiness: $ H(c) = a \cdot t \cdot x = \min(m, n - c) \cdot (n - c) \cdot x $
**Output**
For each test case, output:
- The minimum $ c $ that maximizes $ H(c) $
- The maximum value of $ H(c) $