题目描述

Ngọt - LẦN CUỐI (đi bên em xót xa người ơi)

ඞ

有 $n$ 盏灯，编号为 $1$ 到 $n$，排成一排，初始时全部关闭。你可以进行如下操作任意次（也可以不进行）：

• 选择两个当前都处于关闭状态且不相邻的灯，将它们同时打开。

请判断你能否通过若干次上述操作达到目标状态 $s$，其中 $s_i = 1$ 表示第 $i$ 盏灯是打开的，$s_i = 0$ 表示关闭。

$^\dagger$ 仅当 $i$ 和 $i+1$ 时，灯 $i$ 和灯 $i+1$ 才是相邻的，对于所有 $1 \le i < n$。注意当 $n \ne 2$ 时，灯 $n$ 和灯 $1$ 不相邻。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 50$），表示灯的数量。

第二行包含一个长度为 $n$ 的二进制字符串 $s$，表示最终期望的灯的状态。

输出格式

对于每组测试用例，如果可以通过若干次操作达到目标状态 $s$，则输出一行 "YES"；否则输出 "NO"。

说明/提示

在第一个测试用例中，操作的过程可能如下（初始时 $s$ 全为 $0$）：$\mathtt{0000000000} \to \mathtt{\color{red}{1}0000000\color{red}{1}0} \to \mathtt{1\color{red}{1}00000\color{red}{1}10} \to \mathtt{110\color{red}{1}0\color{red}{1}0110}$。

在第三个测试用例中，不需要进行任何操作。

在第四个测试用例中，无法进行任何操作，但需要第一盏灯是打开的，因此无法达到目标状态。

由 ChatGPT 4.1 翻译

样例

5
10
1101010110
10
1001001110
6
000000
1
1
12
111111111111

YES
NO
YES
NO
YES