Pance is a software engineer that loves to go to the gym. Unfortunately for him, he lives in Skopje, so he has a lot of problems finding a route from his house to the gym, that doesn't require him to cross (jump) over all newly placed antic fences - built around town as part of the project "Skopje 2014".

Skopje is a large city that can be represented as a rectangular grid with width W and length L. You will be given the location of two cells (Xh, Yh) and (Xg, Yg), which represent the location of Pance's house, and the location of the gym. You will also be given a set of horizontal and vertical fences. What is the minimum number of fences that Pance needs to cross in order to get to the gym?

Note: Pance can travel between two cells if they are adjacent. Two cells are adjacent if they share a common edge (either horizontally or vertically).

Input

The first line of input contains one positive integer T (1 <= T <= 10), the number of test cases.

The first line of every test case contains two integers W and L (3 <= W, L <= 100), which represent the width and length of the rectangular grid that represents the city.

The second line contains four integers Xh (0 <= Xh < W), Yh (0 <= Yh < L), Xg (0 <= Xg < W) and Yg (0 <= Yg < L), which represent the location of Pance's house (Xh, Yh), and the location of the gym (Xg, Yg).

The third line contains one integer H (0 <= H <= 100), the number of horizontal fences. Each of the following H lines contains three integers Xi1, Xi2 (0 <= Xi1 < Xi2 <= W) and Yi (1 <= Yi < L), defining the horizontal fences.

The next line contains one integer V (0 <= V <= 100), the number of vertical fences. Each of the following V lines contains three integers Xi (1 <= Xi < W), Yi1 and Yi2 (0 <= Yi1 < Yi2 <= L), defining the vertical fences.

No two fences will overlap, but they may have common endpoints.

Output

For each test case, on a separate line, output the required minimum number of fences that Pance must cross in order to get to the gym.

Constraints

Time limit: 4 seconds
Memory limit: 64 megabytes

Examples

input
1
7 5
1 1 5 4
2
0 5 2
5 7 2
3
4 0 2
3 2 5
5 2 5

output
2

Test case 1: View the image from the task statement.