#T10. 布尔博弈

布尔博弈

题目描述

未来教育的高材生小未和小来正在玩一个游戏。游戏中有一个由 nn 个布尔值组成的字符串,每个布尔值要么为true,要么为false,以长度为 nn 的二进制字符串 ∗^{\text{∗}} 表示(其中 1\texttt{1} 表示真, 0\texttt{0} 表示假)。最初,布尔值之间没有运算符。

小未和小来将轮流在布尔值之间放置 逻辑并(&&) 或 逻辑或(||) 运算符 ,小未先放。需要特别注意的是,运算过程中,逻辑并的优先级高于逻辑或。

一共有 nn 个布尔值,所以游戏将由 n−1n-1 个回合组成。小未的目标是最后的语句结果为 true,而小来的目标是最后的语句结果为 false。给定布尔值字符串,判断如果双方都以最佳方式放置运算符,小未是否会赢。

∗^{\text{∗}} 二进制字符串是指仅由字符 0\texttt{0} 和 1\texttt{1} 组成的字符串。

输入格式

第一行包含 tt ( 1≤t≤1041 \leq t \leq 10^4 ) - 测试用例数。

每个测试用例的第一行包含一个整数 nn ( 2≤n≤2⋅1052 \leq n \leq 2 \cdot 10^5 ) - 字符串长度。

第二行包含长度为 nn 的二进制字符串,由字符 0\texttt{0} 和 1\texttt{1} 组成的二进制字符串。

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

输出格式

对于每个测试用例,如果小未获胜,则输出YES,否则输出 NO。

样例 #1

样例输入 #1

5
2
11
3
010
12
101111111100
10
0111111011
8
01000010

样例输出 #1

YES
NO
YES
YES
NO