G. CS:Go Over
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

This problem has no relation with Problem H Morrow by Morrow.

TSUCE (Time-Space Union of Coding Experts) is preparing to host the TSUCE Programming Duel Cup, an algorithmic programming 1v1 duel between two players!

The competition format is as follows. Please note the meanings of $$$n$$$ and $$$m$$$:

  • Each match is played between two players.
  • A match consists of a regular time + several overtime periods (possibly $$$0$$$ overtime periods). The regular time contains $$$2n$$$ rounds, and one overtime period contains $$$2m$$$ rounds. There is exactly one winner in a single round.
  • The player who wins $$$n + 1$$$ rounds during regular time will win the whole match.
  • If there is a tie after the $$$2n$$$ rounds of regular time (score $$$n:n$$$), the match will enter overtime. The player who wins $$$m + 1$$$ rounds in a single overtime period will win the whole match.
  • If there is still a tie after one overtime period, the match will enter the next overtime period.
  • The final score is the number of rounds won by each player.

Unfortunately, the scorekeeper Little T's database broke down. He only remembers the scores of all $$$k$$$ matches, but he forgot $$$n$$$ and $$$m$$$ related to the format.

Please help him determine whether there exists a valid pair of positive integers $$$n$$$ and $$$m$$$ such that all these scores are valid under this format.

Input

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

The first line of each test case contains an integer $$$k$$$ ($$$1 \le k \le 10^5$$$), representing the number of recorded matches.

Each of the following $$$k$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, b \le 10^{18}, |a - b| \ge 2$$$), representing the score of a match recorded in Little T's database.

It is guaranteed that $$$\sum k \le 3 \times 10^5$$$ over all test cases.

Output

For each test case, if there exists a valid pair of positive integers $$$n$$$ and $$$m$$$ such that all these scores are valid under this format, output a string YES on a single line; otherwise, output a string NO on a single line.

Note that the evaluation is case-insensitive for YES and NO. In other words, when the answer is positive, outputs like yes, YES, Yes, YeS will all be considered correct.

Example
Input
6
3
16 14
10 16
19 22
2
11 16
19 22
5
2 13
16 12
9 13
13 10
20 22
2
5 7
5 9
3
0 5
5 2
11 7
2
6 9
9 6
Output
YES
YES
YES
NO
YES
YES
Note

For the 3rd test case, we can find that $$$n = 12$$$, $$$m = 3$$$ is a valid solution. The matches will go through the following processes:

  • Match 1 is $$$2:13$$$. Player B takes $$$n + 1 = 13$$$ wins first in regular time to end the match.
  • Match 2 is $$$16:12$$$. The regular time ends in a $$$12:12$$$ tie. In the first overtime period, Player A sweeps the opponent $$$4:0$$$, taking $$$m + 1 = 4$$$ wins.
  • Matches 3 and 4 end in regular time with scores of $$$9:13$$$ and $$$13:10$$$, respectively.
  • Match 5 ends in a $$$12:12$$$ tie in regular time. Both the first and second overtime periods end in a $$$3:3$$$ tie, bringing the match to the third overtime with a score of $$$18:18$$$. Finally, Player B defeats the opponent $$$4:2$$$ in the third overtime, resulting in a final score of A $$$20:22$$$ B.