该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你有 $n$ 个花盆依次排成一行，从左到右编号为 $1$ 到 $n$。有些花盆里种有花，有些则是空的。你会得到一个二进制字符串 $s$，用于描述每个花盆是否有花（$s_i = 1$ 表示有花，$s_i = 0$ 表示空）。你还有一些兔子，现在你想为兔子和花一起拍一张漂亮的照片。你想在每个空花盆（$s_i = 0$）里放上一只兔子，对于每只兔子，你可以让它朝左或朝右。

不幸的是，这些兔子很淘气，它们会试图跳到其他花盆，这样会毁了照片。

每只兔子会准备朝它面对的方向跳向下一个花盆，但当以下任一情况发生时，它不会跳：

• 目标花盆里已有兔子；
• 有另一只兔子正朝相反方向准备跳向同一个目标花盆；
• 兔子准备跳出边界（比如位于第 $1$ 个花盆且朝左，或者位于第 $n$ 个花盆且朝右）。

你的目标是为每只兔子选择方向，使得没有任何兔子会真的跳动，好让你有足够时间拍照。你需要判断是否存在一种有效方案，让所有兔子都不会跳。

输入格式

每组测试包含多组数据。第一行为测试用例数 $t$，$1 \leq t \leq 10^4$。

每组测试第一行为一个整数 $n$，$1 \leq n \leq 2 \times 10^5$。

第二行为一个长度为 $n$ 的二进制字符串 $s$，描述每个花盆是否有花。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试用例，如果存在一种安排兔子的方案使得没有兔子会跳动，输出 "YES"；否则输出 "NO"。

输入输出样例 #1

输入 #1

12
4
0100
3
000
8
11011011
5
00100
1
1
5
01011
2
01
7
0101011
7
1101010
5
11001
4
1101
9
001101100

输出 #1

YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO

说明/提示

在第一个测试用例中，一种可行的方案为：第 $1$ 个花盆放一只朝右的兔子，第 $3$ 个花盆放一只朝左的兔子，第 $4$ 个花盆放一只朝左的兔子。没有兔子会跳动，因为：

• 第 $1$ 个花盆的兔子不会跳去第 $2$ 个花盆，因为第 $3$ 个花盆的兔子正朝左；
• 第 $3$ 个花盆的兔子不会跳到第 $2$ 个花盆，因为第 $1$ 个花盆的兔子正朝右；
• 第 $4$ 个花盆的兔子不会跳到第 $3$ 个花盆，因为那里已经有兔子。

在第二个测试用例中，一种可行的方案为：第 $1$ 个花盆放一只朝左的兔子，第 $2$ 个花盆放一只朝右的兔子，第 $3$ 个花盆放一只朝左的兔子。没有兔子会跳动，因为：

• 第 $1$ 个花盆的兔子不会跳，因为左边是边界；
• 第 $2$ 个花盆的兔子不会跳到第 $3$ 个花盆，因为那里已有兔子；
• 第 $3$ 个花盆的兔子不会跳到第 $2$ 个花盆，因为那里已有兔子。

可以证明，第三个测试用例不存在任何有效方案