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.

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.

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.

Sample Input 1

3
4
1 2 3 4
4
1 3 4 2
4
1 4 2 3

Sample Output 1

Yes
Yes
No

Sample Input 2

3
8
4 2 3 4 1 2 2 1
8
3 2 2 3 1 3 3 4
8
2 3 3 2 1 4 1 4

Sample Output 2

Yes
Yes
No

The first test case corresponds to the figure in the Problem Statement.

见题面 Input 部分

见题面 Output 部分