A polygonal chain consists of points p_1,p_2,\dots,p_n where there is a line segment between each two consecutive points.

You are given a set of polygonal chains, and your task is to find out for each chain if it can be represented as a function by rotating the figure. This means that no vertical line intersects the figure in two points.

Input

The first input line has an integer t: the number of polygonal chains. After this, each chain is described as follows:

The first line has an integer n: the number of points. After this, there are n lines, each having two integers x and y. No two consecutive points are the same, and no three consecutive points lie on the same line.

Output

For each polygonial chain, print YES if it can be represented as a function, and NO otherwise.

Example

Input:

2
4
0 0
2 1
3 -1
2 -2
4
0 0
2 1
3 -1
2 0

Output:

YES
NO

Subtask 1 (45 points)

• 1 \le t \le 100
• 2 \le n \le 1000
• -100 \le x,y \le 100

Subtask 2 (55 points)

• 1 \le t \le 100
• 2 \le n \le 10^6
• \sum n \le 10^6
• -10^9 \le x,y \le 10^9