Given a matrix, check if the matrix contains a given key.

The matrix has the following properties:

• Integer in each row is arranged in non-decreasing order from left to right.
• The first integer in every row is greater than the last integer of the previous row.

Examples

Matrix:
1 2 3
4 5 6
7 8 9
Key: 6
Answer: true

Matrix:
1 2 3
4 5 6
7 8 9
10 11 12
Key: 15
Answer: false

Testing

Sample Input

The first line contains 'T' denoting the no. of test cases.

For each test case:

• The first line contains the numbers 'n' and 'm' denoting the number of rows and columns respectively followed by the key.
• The next ‘n’ lines contain ‘m’ space-separated integers denoting elements of a 2-d matrix.

Expected Output

T lines each contain true/false denoting the answer.

Sample Input

2
3 3 6
1 2 3
4 5 6
7 8 9
4 3 15
1 2 3
4 5 6
7 8 9
10 11 12

Expected Output

true
false

Constraints

1 <= T <= 10

1 <= n,m <= 100

0 <= key <= 105

0 <= matrix[i][j] <= 105