Ninja is stuck in a city with ‘N’ colonies, and each colony contains ‘K’ houses. Ninja is currently at the house number “sourceHouse” present in the colony with colony number “sourceColony”. He wants to get to the house with house number “destinationHouse” present in the colony with colony number “destinationColony” as fast as possible.
Since Ninja is a Ninja, he also has a special power by which he can teleport from one house to another within the same colony in 1 second. Also, Ninja can travel from the Kth house of the Mth colony to the 1st house of the (M + 1)th colony and also vice versa in the same time.
Additionally, some houses have secret underground paths to other houses, using which Ninja can travel among houses using this path which also takes 1 second.
You are given a list “secretPaths”, each element of this list contains 4 integers. The first two are for the source house of the path “secretSourceHouse” and “secretSourceColony” denoting the source house number and source colony number respectively. The next 2 integers are for the destination house of the path “secretDestinationHouse” and “secretDestinationColony” denoting the destination house number and destination colony number respectively.
Since the underground paths are secret and having too many paths in the same colony could lead the Ninja community getting caught, there are at most ‘P’ underground paths in each colony (which includes incoming and outgoing underground paths).
Note:
The secret underground paths cannot be used to travel both ways, you can’t travel from destination to source.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains four space-separated integers, ‘N’, ‘K’, ‘S’ and ‘P’ denoting the number of colonies, number of houses in each colony, the number of secret underground paths and the maximum number of underground paths in a colony respectively.
The next line contains four space-separated integers “sourceHouse”, “sourceColony”, “destinationHouse” and “destinationColony” denoting the house number and colony number of Ninja’s initial position and house number and colony number of the destination house respectively.
The next ‘S’ line contains four space-separated integers each denoting the arrays “secretPaths[i]”.
Output Format :
For each test case, return an integer denoting the minimum time Ninja takes.
Output for each test case will be printed in a new line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints:
1 <= T <= 100
1 <= N <= 100
1 <= K <= 10^9
1 <= P <= 50
0 <= S <= (P * N) / 2
Where ‘T’ denotes the number of test cases,
‘N’ denotes the number of colonies,
‘K’ denotes the number of houses in each colony,
‘P’ denotes the maximum number of underground paths in a colony and
‘S’ denotes the number of underground paths.
Time Limit: 1 sec
Sample Input 1 :
1
5 5 1 1
3 1 3 5
1 1 5 5
Sample Output 1:
3
Explanation For Sample Output 1:
The path Ninja follows would be (colony number, house number) = (1, 3) -> (1, 1) -> (5, 5) -> (5, 3).
The first teleport from (1, 3) -> (1, 1) can be performed as both of the houses are in the first colony.
The next transition (1, 1) -> (5, 5) can be done using the underground path and the last one from (5, 5) -> (5, 3) can be done as both the houses are in the fifth colony.
Sample Input 2 :
2
10 5 2 2
2 3 4 10
1 1 5 10
5 8 4 7
7 8 0 0
8 4 6 7
Sample Output 2 :
7
6