Problem Description

Because of Covid-19, Kanade needs to report every time when entering and leaving school. Now you want to check if Kanade's reports on a certain day are correct.

A sequence of reports is correct if and only if there does not exist two consecutive and same reports.

Input

There are $T$ test cases in this problem.

The first line has one integer $T$.

For every test case:

The first line has one integer $n$ which denotes the number of times Kanade reported on a certain day.

The second line has $n$ integers $a_1,a_2,a_3,\cdots,a_n$, $a_i$ denotes the type of the $i$-th report. $a_i=0$ denotes a leaving school report and $a_i=1$ denotes an entering school report.

$1\leq T\leq 100$

$3\leq n\leq 50$

$0\leq a_i\leq 1$

Output

For every test case, output ``YES'' if Kanade's reports are correct, otherwise output ``NO'' (without quotes)

4
3
1 1 1
3
1 0 1
5
0 1 0 1 0
4
1 0 1 1

NO
YES
YES
NO