{"raw_statement":[{"iden":"statement","content":"On Planet E, people enjoy playing snooker!\n\nUnlike 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.\n\nThe goal is to move the ball from $(x_0, y_0)$ to $(x_1, y_1)$, with exactly $k$ bounces from the table walls.\n\nThis 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.\n\nCan you help the people on Planet E to find the shortest distance the ball has to travel to achieve the goal?\n\nThe first line contains a positive integer $T$ ($T <= 100$), the number of testcases.\n\nEach 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.\n\nFor each testcase, output a single line consisting of the shortest distance the ball has to travel, corrected to $2$ decimal places.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"For each testcase, output a single line consisting of the shortest distance the ball has to travel, corrected to $2$ decimal places."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ m, n \\in \\mathbb{Z}^+ $ be the dimensions of the rectangular table.  \nLet $ (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 $.  \nLet $ k \\in \\mathbb{Z}_{\\ge 0} $ be the exact number of wall bounces.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. $ 2 \\le m, n \\le 100 $  \n3. $ 0 < x_0, x_1 < m $, $ 0 < y_0, y_1 < n $  \n4. $ 0 \\le k \\le 100 $  \n\n**Objective**  \nFind 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.  \n\nFor 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:  \n$$\n(x_1', y_1') = \n\\begin{cases}\n(2am \\pm x_1, 2bn \\pm y_1) & \\text{based on parity of } a, b \\\\\n\\end{cases}\n$$  \nMore precisely:  \n- If $ a $ is even: $ x_1' = x_1 + 2am $  \n- If $ a $ is odd: $ x_1' = (2a+1)m - x_1 $  \n- If $ b $ is even: $ y_1' = y_1 + 2bn $  \n- If $ b $ is odd: $ y_1' = (2b+1)n - y_1 $  \n\nThen, for all $ (a,b) $ such that the total number of reflections is exactly $ k $, compute:  \n$$\nd_{a,b} = \\sqrt{(x_1' - x_0)^2 + (y_1' - y_0)^2}\n$$  \nThe answer is:  \n$$\n\\min_{\\substack{a,b \\in \\mathbb{Z} \\\\ |a| + |b| = k \\\\ a + b \\equiv k \\pmod{2}}} d_{a,b}\n$$","simple_statement":"Find the shortest path for a ball to go from (x0, y0) to (x1, y1) on a rectangular table of size m×n, bouncing exactly k times off the walls, with perfect reflections. Output the distance rounded to 2 decimal places.","has_page_source":false}