You have an n*m matrix with start position at (0, 0) and end position at (n, m).

There are c circles with centers inside the matrix, each with radius r. You are given the center co-ordinates (x, y) of each of those circles.

Note: You can move from any point to any of its 8 adjecent neighbours.

Find if there is a way to travel from start to end without touching any of these circles.

Example

n: 5
m: 4
r: 1
circles(x, y): [(0, 2), (2, 3), (3, 0), (4, 1)]
Answer: True
Explanation: The valid path is shown in the diagram above.

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has the following lines:

• The first line has four space separated integers: n, m, c and r.
• The next c lines has 2 space separated integers, x and y, denoting the center of each circle.

Output Format

For each test case, the output contains a line with one integer 1 or 0, depending of whether there is a valid path or not respectively.

Sample Input

4
5 4 4 1
0 2
2 3
3 0
4 1
5 4 4 1
0 2
2 3
3 0
4 2
1 1 0 2
1 1 1 1
0 1

Expected Output

1
0
1
0

Constraints

1 <= T <= 10
1 <= n, m <= 300
1 <= c <= 100
1 <= r <= 20
0 <= x <= n
0 <= y <= m