Problem Statement

There are $N$ vertices on a circumference. The vertices are numbered $1$ to $N$ in clockwise order, and Vertex $i$ has an integer $A_i$ written on it, where $A_i$ is $1$, $2$, $3$, or $4$. Here, $A$ contains each of $1$, $2$, $3$, and $4$ at least once.

Consider making a tree by adding $N-1$ edges connecting these $N$ vertices. Here, the following conditions must be satisfied.

• If Vertices $x$ and $y$ are directly connected by an edge, $|A_x-A_y|=1$.
• When the edges are drawn as segments, no two of them intersect except at an endpoint.

For instance, the figure below shows a tree that satisfies the conditions:

Determine whether it is possible to construct a tree that satisfies the conditions.

Solve $T$ test cases for each input file.

Constraints

• $1 \leq T \leq 75000$
• $4 \leq N \leq 300000$
• $1 \leq A_i \leq 4$
• $A$ contains each of $1$, $2$, $3$, and $4$ at least once.
• The sum of $N$ in one input file does not exceed $300000$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is in the following format:

N
A_1 A_2 \cdots A_N

Output

For each case, print Yes if it is possible to construct a tree that satisfies the conditions, and No otherwise.