問題文

0, 1, ? からなる長さ $N$ の文字列 $S$ が与えられます。

$S$ に含まれるすべての ? をそれぞれ 0 か 1 に変更することで、$S$ の中に同じ文字が三連続で現れないようにすることができるか判定してください。ただし $S$ の末尾と先頭は繋がっているものとします。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

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

ただし test$_i$ は $i$ 番目のテストケースを表し、以下の形式で与えられる。

$N$
$S$

• $T, N$ は整数
• $S$ は 0, 1, ? からなる長さ $N$ の文字列
• $1 \le T \le 5 \times 10^4$
• $3 \le N \le 10^5$
• すべてのテストケースの $N$ の総和は $2 \times 10^5$ を超えない

出力

$S$ の中に同じ文字が三連続で現れないようにできるなら Yes を、そうでなければ No を出力してください。 最後に改行してください。

サンプル

3
3
1?1
5
11?00
4
1101

Yes
No
No