题目描述

你有 $n$ 个花盆从左到右排成一行并编号为 $1$ 到 $n$。有些花盆里有花（用字符 $1$ 表示），有些是空的（用字符 $0$ 表示）。用二进制字符串 $s$ 描述这些花盆的情况：当 $s_i=1$ 时第 $i$ 个花盆有花，当 $s_i=0$ 时第 $i$ 个花盆为空。你还有一些兔子，想和花一起拍一张好看的合影。你想在每个空花盆（$s_i=0$）里放一只兔子，并且每只兔子可以选择面向左或面向右。

不幸的是，这些兔子很淘气，可能会跳动，从而破坏照片。每只兔子会准备跳向其面向方向的下一个花盆，但在以下两种情况下不会跳：

• 目标格子里已经有兔子，
• 有另一只兔子也准备从相反方向跳入同一个格子（即两只兔子同时准备跳入同一格子）。

另外，兔子不会跳出边界（位于格子 $1$ 且面向左的兔子不会跳出界外，位于格子 $n$ 且面向右的兔子也不会跳出界外）。

你的目标是为每只兔子选择一个朝向，使得没有任何兔子会跳，从而你可以慢慢拍照。判断是否存在这样的朝向安排使得所有兔子都永远不跳。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$）——测试用例数。随后是 $t$ 个测试用例。

每个测试用例包含两行：

• 第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$）；
• 第二行包含一个长度为 $n$ 的二进制字符串 $s$，表示花盆的状态（$s_i\in{0,1}$）。

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

输出格式

对于每个测试用例，如果存在一种兔子朝向的布置使得没有兔子会跳，则输出 YES，否则输出 NO。大小写不限。

样例输入

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

样例输出

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

说明

样例 1 解释

一种合法的布置是：位置 $1$ 的兔子朝右，位置 $3$ 的兔子朝左，位置 $4$ 的兔子朝左。可以验证没有兔子会跳。

样例 2 解释

一种合法的布置是：位置 $1$ 朝左，位置 $2$ 朝右，位置 $3$ 朝左，同样没有兔子会跳。

样例 3 解释

无任何合法布置。