Hogwarts School of Witchcraft and Wizardry has a circular lane having N towers numbered 1 to N. Towers i and i+1 are adjacent to each other for 1 ≤ i < N and also towers 1 and N are adjacent to each other. Each of these towers has exactly F number of floors, numbered 1,2,3,..,F-1,F from bottom to top. Floors i and i+1 in a tower are adjacent to each other and it takes one second to move between them. It also takes one second to move between floor 1 of a tower and floor 1 of its adjacent tower. Apart from these, there are M bridges designed for a quick escape in case of a Death Eater attack, each of which connects two floors of different towers. Each of these bridges is given as bi fi bj fj t, meaning it takes t seconds to move along this bridge that connects the floor fi of tower bi and the floor fj of tower bj. All ways are bidirectional.

Given (qbi,qfi) and (qbj,qfj), find the minimum time in seconds it takes to reach floor qfj of tower qbj, starting from floor qfi of tower qbi. You have to answer a lot of such queries.

Input (STDIN):

The first line contains the number of test cases T. T cases follow. Each test case consists of N F M in the first line. N is the number of towers, F is the number of floors in each tower and M is the number of bridges. M lines follow, each of the form bi fi bj fj t, as mentioned in the problem statement. Next line contains Q, the number of queries and Q lines follow, each of the form qbi qfi qbj qfj.

Output (STDOUT):

For each query of the form qbi qfi qbj qfj, output one line denoting the minimum time in seconds it takes to reach the floor qfj of tower qbj, starting from the floor qfi of tower qbi.

Constraints:

1 ≤ T ≤ 3

2 ≤ N, M ≤ 100

2 ≤ F ≤ 1,000,000

1 ≤ t ≤ 1,000,000

1 ≤ Q ≤ 100,000

1 ≤ bi, bj, qbi, qbj ≤ N

1 ≤ fi, fj, qfi, qfj ≤ F

Sample Input:

1

5 4 3

1 3 2 4 3

2 3 3 3 2

3 4 5 3 1

5

1 3 2 3

1 3 3 2

1 1 3 4

3 3 4 4

4 3 4 4

Sample Output:

4

5

4

6

1