L. In Filtration 3
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Maddy is still purging Baddy's evil army... for the third time!

The game takes place on an infinite Cartesian plane, which you may imagine as an infinite chessboard. Baddy controls $$$n$$$ stationary cannons, placed at $$$(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$$$.

Under Chinese chess rules, a cannon attacks by jumping over a screen. If cannons $$$A$$$ and $$$B$$$ share a row or column and exactly one other cannon $$$C$$$ lies between them, $$$A$$$ attacks $$$B$$$ (and $$$B$$$ attacks $$$A$$$). Cannon $$$C$$$ is their "screen."

At each step, Maddy may destroy a cannon that is not currently attacked by any other cannon. The destroyed cannon is immediately removed; it can no longer attack or serve as a screen.

Maddy wants to destroy all $$$n$$$ cannons. Does there exist an order of destruction that clears the board?

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$), the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$), the number of cannons.

Each of the next $$$n$$$ lines contains two integers $$$x_i,y_i$$$ ($$$-10^9 \le x_i,y_i \le 10^9$$$), the position of cannon $$$i$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$. All cannon positions within a test case are distinct.

Output

For each test case, output YES if some valid destruction order clears the board, or NO otherwise.

The answer is case-insensitive; for example, yes, YES, Yes, and YeS are all accepted as affirmative answers.

Example
Input
3
3
0 0
0 1
0 2
4
0 0
1 0
2 0
3 0
8
2 0
0 1
1 1
2 1
1 2
2 2
3 2
1 3
Output
YES
NO
NO
Note

Sample 1 Explanation

In the first test case, the three cannons share a column. Initially, $$$(0,0)$$$ and $$$(0,2)$$$ attack each other over the screen at $$$(0,1)$$$, while $$$(0,1)$$$ is unattacked. Destroy $$$(0,1)$$$ first. Then the other two are unattacked and may be destroyed in either order.

In the second test case, four cannons share a row. Initially, $$$(0,0)$$$ and $$$(2,0)$$$ attack each other over $$$(1,0)$$$; $$$(1,0)$$$ and $$$(3,0)$$$ attack each other over $$$(2,0)$$$. Thus every cannon is attacked, none can be destroyed, and the answer is NO.