Problem Statement

You are given a string $S$ of length $N$ consisting of 0, 1, and ?.

Determine whether it is possible to change every ? in $S$ to either 0 or 1 so that the same character does not appear three times in a row in $S$. Here, the end and the beginning of $S$ are considered to be connected.

You are given $T$ test cases; find the answer for each of them.

Input

$T$
test$_1$
$\vdots$
test$_T$

Here, test$_i$ represents the $i$-th test case, given in the following format.

$N$
$S$

• $T, N$ are integers
• $S$ is a string of length $N$ consisting of 0, 1, and ?
• $1 \le T \le 5 \times 10^4$
• $3 \le N \le 10^5$
• The sum of $N$ over all test cases does not exceed $2 \times 10^5$

Output

Print Yes if it is possible to prevent the same character from appearing three times in a row in $S$, and No otherwise. Print a newline at the end.

Sample

3
3
1?1
5
11?00
4
1101

Yes
No
No