As Intra SUST Programming Contest-2024 is approaching, problem-setters are looking for some easy but interesting problems. So, here is a problem for you. There is an infinite 2D grid. You will start from a coordinate $$$(s_x,s_y)$$$ and reach a coordinate $$$(t_x,t_y)$$$, possibly the same coordinate. In one move, you can go left, right, up, or down from your current position. You need to find the minimum number of operations to reach the target coordinate. Sounds too easy, right?
So, here is a constraint for you. You can not move more than $$$k$$$ times consecutively in the same direction. Can you solve it now?
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ – denoting the number of test cases.
Following $$$t$$$ lines each contain $$$5$$$ integers $$$s_x,s_y,t_x,t_y,k (-10^9 \leq s_x,s_y,t_x,t_y \leq 10^9, 1 \leq k \leq 10^9)$$$.
Output one integer for each case, the minimum number of moves required.
5 0 0 -5 10 100 1 1 56 57 5 -3 10 2 65 5 1000000000 -1000000000 1000000000 -1000000000 1 0 0 2 4 1
15 111 66 0 8
In the first test case, you can move $$$5$$$ times left and then $$$10$$$ times up to reach the destination.
In the second test case, you can move $$$5$$$ times right, then $$$5$$$ times up, then $$$5$$$ times right, then $$$5$$$ times up and so on to reach $$$(56,56)$$$ and finally move up to reach $$$(56,57)$$$.
In the fourth test case, you don't need to move at all.
