Given a sequence of $N$ positive integers, determine whether there exists an arithmetic subsequence of length at least three.

Input

The first line contains a positive integer $T$, representing the number of test cases.

For each test case, the first line contains a positive integer $N$, representing the length of the sequence. The second line contains $N$ positive integers, representing the elements of the sequence in order.

Output

For each test case, output YES or NO on a single line.

Examples

Input 1

3
4
4 3 2 1
2
1 100
5
1 17 9 18 17

Output 1

YES
NO
YES

Subtasks

For $20\%$ of the data: $N\le 100$.

For $40\%$ of the data: $N\le 10^3$.

For $100\%$ of the data: $1\le T \le 10$, $1\le N\le 2\times 10^4$, and the numbers in the sequence are $\le 2\times 10^4$.