311215: CF1951A. Dual Trigger

A. Dual Triggertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputNgọt - LẦN CUỐI (đi bên em xót xa người ơi)ඞ

There are $n$ lamps numbered $1$ to $n$ lined up in a row, initially turned off. You can perform the following operation any number of times (possibly zero):

• Choose two non-adjacent${}^\dagger$ lamps that are currently turned off, then turn them on.

Determine whether you can reach configuration $s$, where $s_i = 1$ means the $i$-th lamp is turned on, and $s_i = 0$ otherwise.

${}^\dagger$ Only lamp $i$ and $i + 1$ are adjacent for all $1 \le i < n$. Note that lamp $n$ and $1$ are not adjacent when $n \ne 2$.

Input

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 50$) — the number of lamps.

The second line of each test case contains a binary string $s$ of size $n$ — the final desired configuration.

Output

For each test case, print on one line "YES" if we can reach the configuration $s$ via applying the given operation any number of times. Otherwise, print "NO".

ExampleInput

5
10
1101010110
10
1001001110
6
000000
1
1
12
111111111111

Output

YES
NO
YES
NO
YES

Note

In the first test case, the sequence of operation could have been as follows (note that initially $s$ is all zero): $\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}$.

In the third test case, we don't have to do any operation.

In the fourth test case, we cannot do any operation, but we need the first lamp to be on. Therefore, it is impossible to achieve the desired state.

题目大意：
题目名为“双触发”，有一个排成一行的灯，编号为1到n，初始状态是关闭的。你可以执行以下操作任意多次（可能为零次）：
- 选择两个非相邻的且当前处于关闭状态的灯，然后将它们打开。
要确定是否可以达到配置s，其中s_i = 1表示第i个灯是打开的，s_i = 0则表示关闭。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 1000）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 50）——灯的数量。
- 每个测试用例的第二行包含一个长度为n的二进制字符串s——最终期望的配置。

输出：
- 对于每个测试用例，如果可以通过应用给定操作任意多次达到配置s，则在一行中打印“YES”。否则，打印“NO”。

示例：
输入：
```
5
10
1101010110
10
1001001110
6
000000
1
1
12
111111111111
```
输出：
```
YES
NO
YES
NO
YES
```

注意：
- 在第一个测试案例中，操作序列可能如下（注意最初s全为零）：`0000000000 -> 1000000010 -> 1100000110 -> 1101000110`。
- 在第三个测试案例中，我们不需要执行任何操作。
- 在第四个测试案例中，我们无法执行任何操作，但需要第一个灯是打开的。因此，无法达到期望状态。题目大意： 题目名为“双触发”，有一个排成一行的灯，编号为1到n，初始状态是关闭的。你可以执行以下操作任意多次（可能为零次）： - 选择两个非相邻的且当前处于关闭状态的灯，然后将它们打开。 要确定是否可以达到配置s，其中s_i = 1表示第i个灯是打开的，s_i = 0则表示关闭。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 1000）——测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 50）——灯的数量。 - 每个测试用例的第二行包含一个长度为n的二进制字符串s——最终期望的配置。 输出： - 对于每个测试用例，如果可以通过应用给定操作任意多次达到配置s，则在一行中打印“YES”。否则，打印“NO”。 示例： 输入： ``` 5 10 1101010110 10 1001001110 6 000000 1 1 12 111111111111 ``` 输出： ``` YES NO YES NO YES ``` 注意： - 在第一个测试案例中，操作序列可能如下（注意最初s全为零）：`0000000000 -> 1000000010 -> 1100000110 -> 1101000110`。 - 在第三个测试案例中，我们不需要执行任何操作。 - 在第四个测试案例中，我们无法执行任何操作，但需要第一个灯是打开的。因此，无法达到期望状态。