Shreckless

Limits: 2 sec., 512 MiB

Lord Farquaad has a table \(a\) of integers with \(n\) rows and \(m\) columns. Since he is obsessed with order, he wants each row of the table to be sorted in nondecreasing order.

Shrek, who finds Farquaad’s need for order ridiculous, has other plans. He can arbitrarily permute the numbers in each column, and wants to make sure that not a single row in the table is nondecreasing. Can he achieve his goal?

An array \(a_1, a_2, \ldots, a_k\) is called nondecreasing, if \(a_1 \leq a_2 \leq \ldots \leq a_k\).

Input

Each test consists of multiple test cases. The first line contains a single integer \(t\) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integer \(n, m\) — dimensions of the table.

The \(i\)-th of the next \(n\) lines contains \(m\) integers \(a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}\) — elements of the \(i\)-th row.

Output

For each test case, if Shrek can make each row not nondecreasing, output YES. Else, output NO.

Constraints

\(1 \leq t\leq 2\cdot 10^4\),

\(2 \leq n, m \leq 10^5\),

\(n\cdot m \leq 2\cdot 10^5\),

the sum of \(n\cdot m\) over all test cases doesn’t exceed \(2\cdot 10^5\),

\(1 \leq a_{i, j} \leq 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 2 2 69 69 2024 42 3 3 1 1 1 1 1 1 2 2 2 3 4 1 1 1 1 1 1 1 1 2 2 2 2	YES NO YES

Notes

In the first test case, initially the first row is \([69, 69]\), and therefore is nondecreasing. However, Shrek can swap the numbers in the first column, getting

2024	69
69	42

In the second test case, there is no way to rearrange columns to make each row not nondecreasing.

In the third test case, Shrek can rearrange columns as follows:

1	1	2	1
1	2	1	1
2	1	1	2