Alice 和 Bob 正在玩游戏。有一个 $$$n$$$ 布尔值列表,每个布尔值要么为真,要么为假,以长度为 $$$n$$$ 的二进制字符串 $$$^{\text{∗}}$$$ 给出(其中 $$$\texttt{1}$$$ 表示 true,$$$\texttt{0}$$$ 表示 false)。最初,布尔值之间没有运算符。
Alice 和 Bob 将轮流放置和/或在布尔值之间,Alice 首先进行。因此,游戏将由 $$$n-1$$$ 回合组成,因为存在 $$$n$$$ 布尔值。 Alice 的目标是最终语句评估为 true,而 Bob 的目标是评估为 false。给定布尔值列表,确定如果两个玩家都发挥最佳状态,Alice 是否会获胜。
要计算最终表达式,请重复执行以下步骤,直到语句包含单个 true 或 false:
- 如果语句包含 and 运算符,请选择任意一个并将其周围的子表达式替换为其计算结果。
- 否则,该语句包含 or 运算符。选择任意一个并将 or 周围的子表达式替换为其计算值。
输入
第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 字符串的长度。
第二行包含长度为 $$$n$$$ 的二进制字符串,由字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ - 布尔值列表组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果 Alice 获胜,则输出“YES”(不带引号),否则输出“NO”(不带引号)。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yES”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
5 2 11 3 010 12 101111111100 10 0111111011 8 01000010
输出 #1
YES NO YES YES NO
注意
在第一个测试用例中,Alice 可以将 和 放在两个布尔值之间。由于没有其他地方可以放置运算符,游戏结束,爱丽丝获胜,因为 true 和 true 都是 true。
在第二个测试用例中,Alice 可以将 or 放置在中间 true 和左侧 false 之间。 Bob 可以将 和 放置在中间 true 和右侧 false 之间。假或真又假的陈述是假的。
请注意,这些示例可能不是 Alice 或 Bob 的最佳策略。