CSES - Datatähti Open 2019 - Function
  • Time limit: 1.00 s
  • Memory limit: 512 MB
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$