On Planet E, people enjoy playing snooker!
Unlike snooker on Earth, there is only one ball on Planet E, and no pockets on the table. Let the length of the table be $m$ and the width of the table be $n$. Then the positions on the table can be represented by $(x, y)$ where $0 <= x <= m$ and $0 <= y <= n$. We view the ball as a point without radius.
The goal is to move the ball from $(x_0, y_0)$ to $(x_1, y_1)$, with exactly $k$ bounces from the table walls.
This figure demonstrates 2 bounces. The ball moves in straight line and the reflection angle must be the same. Note that if the ball moves to a corner, it will move back in the exactly opposite direction with 2 bounces. See testcase 2 in the sample.
Can you help the people on Planet E to find the shortest distance the ball has to travel to achieve the goal?
The first line contains a positive integer $T$ ($T <= 100$), the number of testcases.
Each testcase contains 7 integers $m, n, x_0, y_0, x_1, y_1, k$ ($2 <= m <= 100$, $2 <= n <= 100$, $0 < x_i < m$ and $0 < y_i < n$ for $i = 0, 1$, and $0 <= k <= 100$), representing the table size (length $m$, width $n$) and the goal $(x_0, y_0)$ to $(x_1, y_1)$ with exactly $k$ bounces.
For each testcase, output a single line consisting of the shortest distance the ball has to travel, corrected to $2$ decimal places.
## Input
The first line contains a positive integer $T$ ($T <= 100$), the number of testcases.Each testcase contains 7 integers $m, n, x_0, y_0, x_1, y_1, k$ ($2 <= m <= 100$, $2 <= n <= 100$, $0 < x_i < m$ and $0 < y_i < n$ for $i = 0, 1$, and $0 <= k <= 100$), representing the table size (length $m$, width $n$) and the goal $(x_0, y_0)$ to $(x_1, y_1)$ with exactly $k$ bounces.
## Output
For each testcase, output a single line consisting of the shortest distance the ball has to travel, corrected to $2$ decimal places.
[samples]
**Definitions**
Let $ m, n \in \mathbb{Z}^+ $ be the dimensions of the rectangular table.
Let $ (x_0, y_0), (x_1, y_1) \in \mathbb{R}^2 $ be the start and target points, with $ 0 < x_0, x_1 < m $, $ 0 < y_0, y_1 < n $.
Let $ k \in \mathbb{Z}_{\ge 0} $ be the exact number of wall bounces.
**Constraints**
1. $ 1 \le T \le 100 $
2. $ 2 \le m, n \le 100 $
3. $ 0 < x_0, x_1 < m $, $ 0 < y_0, y_1 < n $
4. $ 0 \le k \le 100 $
**Objective**
Find the minimal Euclidean distance of a path from $ (x_0, y_0) $ to $ (x_1, y_1) $ with exactly $ k $ reflections off the table boundaries, using the method of image reflections.
For each pair of integers $ (a, b) \in \mathbb{Z}^2 $ such that $ |a| + |b| = k $ and $ a + b \equiv k \pmod{2} $, define the image point:
$$
(x_1', y_1') =
\begin{cases}
(2am \pm x_1, 2bn \pm y_1) & \text{based on parity of } a, b \\
\end{cases}
$$
More precisely:
- If $ a $ is even: $ x_1' = x_1 + 2am $
- If $ a $ is odd: $ x_1' = (2a+1)m - x_1 $
- If $ b $ is even: $ y_1' = y_1 + 2bn $
- If $ b $ is odd: $ y_1' = (2b+1)n - y_1 $
Then, for all $ (a,b) $ such that the total number of reflections is exactly $ k $, compute:
$$
d_{a,b} = \sqrt{(x_1' - x_0)^2 + (y_1' - y_0)^2}
$$
The answer is:
$$
\min_{\substack{a,b \in \mathbb{Z} \\ |a| + |b| = k \\ a + b \equiv k \pmod{2}}} d_{a,b}
$$