您有 $$$n$$$ 花盆排列成一行,编号从 $$$1$$$ 到 $$$n$$$ 从左到右。有些花盆里装着花,有些花盆里是空的。您将获得一个二进制字符串 $$$s$$$ 来描述哪些花盆包含鲜花 ($$$s_i = 1$$$) 以及哪些花盆是空的 ($$$s_i = 0$$$)。你也有一些兔子,你想拍一张兔子和花的漂亮照片。您想将兔子放入每个空罐子中 ($$$s_i = 0$$$),并且对于每只兔子,您可以将其向左或向右放置。不幸的是,兔子很调皮,它们会尝试跳跃,这会破坏画面。
每只兔子都会准备按照它们所看的方向跳入下一个罐子,但如果该罐子里已经有一只兔子,或者有另一只兔子准备从对面跳进同一个罐子,它们就不会跳。兔子不会跳出边界(一只兔子在 $$$1$$$ 罐子里向左看不会跳,同样,一只兔子在 $$$n$$$ 罐子里向右看)。
你的目标是选择兔子的方向,让它们永远不会跳跃,这样你就可以慢慢拍照。您需要确定是否存在有效的兔子排列方式,使得兔子不会跳跃。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含一个大小为$$$n$$$的二进制字符串$$$s$$$,表示已占用和空的罐子。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印“是“如果存在满足条件的兔子配置,并且”NO”否则。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。
示例
输入复制
12401003000811011011500100115010112017010101171101010511001411019001101100
输出复制
YESYESNOYESYESYESYESYESYESYESNONO
注意
展示台链接
在第一个测试用例中,有效的配置之一是将一只兔子向右看的位置$$$1$$$,一只向左看的兔子在位置$$$3$$$,以及一只向左看的兔子在位置$$$4$$$。自从以下情况以来,没有兔子会移动:
- 罐子 $$$1$$$ 的兔子不会移动到罐子 $$$2$$$,因为罐子 $$$3$$$ 的兔子正在向左看。
- 罐子 $$$3$$$ 的兔子不会移动到罐子 $$$2$$$,因为罐子 $$$1$$$ 的兔子正在向右看。
- 罐子 $$$4$$$ 中的兔子不会移动到罐子 $$$3$$$ 中,因为那里有一只兔子。
在第二个测试用例中,有效的配置之一是将一只兔子向左看的位置$$$1$$$,一只向右看的兔子在位置$$$2$$$,以及一只向左看的兔子在位置$$$3$$$。自从以下情况以来,没有兔子会移动:
- 罐子 $$$1$$$ 中的兔子不会移动,因为它正在看左边界。
- 罐子 $$$2$$$ 中的兔子不会移动到罐子 $$$3$$$ 中,因为那里有一只兔子。
- 罐子 $$$3$$$ 中的兔子不会移动到罐子 $$$2$$$ 中,因为那里有一只兔子。
可以证明,第三个测试用例中没有有效的兔子排列。