Digo has completed all his initial assignments and is now eyeing for a promotion in the CIA office. There is only one seat available for which there are two contenders, Digo and his arch rival Sharry. Both are equally qualified for the promotion and their interviewer finds himself unable to chose between the two of them. Finally he decided to settle it by allowing the two gentlemen to play a game and see who wins it.

In the game, there is an infinite grid, with certain cells filled with checkers. Each checker occupies exactly one cell, and the cells are 0-indexed. The positions of the checkers are given in the form of Cartesian coordinates (x, y).

For example a grid with 5 checkers placed at positions {(1, 0), (1, 2), (2, 5), (4, 2), (4, 4)} would look like:

There are an infinite number of diagonals of the form y = x + k, where k is an integer, drawn on this grid. Each diagonal can be uniquely identified by the value of this 'k', which is known as the index of the diagonal. There is at most one checker on every diagonal. In one turn, a person can chose a checker and move it along the diagonal it lies on, in the south-west direction only (i.e. towards decreasing coordinates). The checkers cannot be moved outside the first quadrant (i.e., their coordinates can never be made negative throughout the game). Whenever a person moves a checker, the checker lying on the next higher occupied diagonal moves an equal distance along the north-east direction. A diagonal with a greater index is said to be higher than a diagonal with a smaller index. Thus if the person moves the checker at position (4, 2) {diagonal index - 2} one cell south-west, the checker at position (1, 0) {diagonal index -1} moves one cell north-east.

The final position of the checkers after this move would be:

Note that if a person moves the checker lying on the highest occupied diagonal (the checker at position (2, 5) in our case), no other checker is disturbed.

The game ends when no move is possible. The last person to make a move wins. Sharry is an over-confident guy and allows Digo to move first. Help Digo determine whether he will win the game or not.

NOTE: Large input files. Use faster I/O.

Input

The first line contains T, the number of test cases.
The first line of every test case contains N, the number of checkers on the grid. This is followed by N lines. The ith line contains two integers x[i] and y[i], which are the coordinates of the ith checker.

Output

For every test case output a single line containing "Yes" if it is possible for Digo to win the game, or "No" otherwise. (quotes added for clarity)

Constraints

1 <= T <= 20
1 <= N <= 10000
0 <= x[i], y[i] <= 1000000000

Example

Input:
1
5
1 0
1 2
2 5
4 2
4 4

Output:
Yes

---

hide comments

	Piyush Kumar: 2016-06-22 15:03:16 Without the images,its still a bit unclear. I am getting WA. [Simes]: Images added. Last edit: 2022-05-31 21:45:39
	Mitch Schwartz: 2014-07-01 18:33:21 I think the images aren't necessary to understand the problem. Problem statement updated, specifically: "A diagonal with a Greater value of index is said to be higher than a diagonal with a greater index." -> "A diagonal with a greater index is said to be higher than a diagonal with a smaller index." "{diagonal index 2}" -> "{diagonal index -2}" "{diagonal index 1}" -> "{diagonal index -1}" But there is still a point that is not clear: After reading up to "Help Digo determine whether he will win the game or not", my assumption is that both players play optimally (as with other problems of this type), but then in output section we are told 'For every test case output a single line containing "Yes" if it is possible for Digo to win the game, or "No" otherwise', which could mean that Digo only wants to know if it is possible for him to win against a non-necessarily-optimally-playing player. (Anyone who has solved the problem can clarify, if the psetter doesn't.) Edit: After re-reading the problem, I realise that I made an assumption without thinking about it: that moving a distance of 1 "cell" changes both the x- and y-coordinates by 1. This would be a clarified by the images. But I would be surprised if it's a wrong assumption. Last edit: 2014-07-02 06:57:48
	wisfaq: 2014-07-01 14:37:48 It seems that the domain where the images were hosted doesn't exist any more. psetter do you have private copies? --ans(Francky)--> Unluckily, I don't have them. I'll send a mail to psetter ; problem hidden waiting for fix. (edit : Mitch proposed to edit the description, it should fix part of the issue) Last edit: 2014-07-01 18:07:30
	NISHANT RAJ: 2014-06-05 06:28:41 I am also unable to see the image.. i think images were removed from server
	Bhavik: 2014-06-04 15:26:26 i am unable to see images!!am i the only one or others are also facing the same problem?? Last edit: 2014-06-04 15:31:07