您有一个长度为 $$$n$$$ 的二进制字符串$$$^{\text{∗}}$$$ $$$s$$$,Iris 为您提供了另一个长度为 $$$n-1$$$ 的二进制字符串 $$$r$$$。
Iris 要和你玩一个游戏。游戏过程中,您将对$$$s$$$执行$$$n-1$$$操作。在第 $$$i$$$ 操作中 ($$$1 \le i \le n-1$$$):
- 首先,选择一个索引 $$$k$$$ 使得 $$$1\le k\le |s| - 1$$$ 和 $$$s_{k} \neq s_{k+1}$$$。如果不可能选择这样的指数,你就输了;
- 然后,将 $$$s_ks_{k+1}$$$ 替换为 $$$r_i$$$。请注意,这会将 $$$s$$$ 的长度减少 $$$1$$$。
如果所有 $$$n-1$$$ 操作均成功执行,则您获胜。
确定你是否有可能赢得这场比赛。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 10^5$$$) — $$$s$$$ 的长度。
第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$ ($$$s_i=\mathtt{0}$$$ 或 $$$\mathtt{1}$$$)。
第三行包含长度为 $$$n-1$$$ 的二进制字符串 $$$r$$$ ($$$r_i=\mathtt{0}$$$ 或 $$$\mathtt{1}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,如果您可以赢得游戏,则打印“YES”(不带引号),否则打印“NO”(不带引号)。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
6 2 11 0 2 01 1 4 1101 001 6 111110 10000 6 010010 11010 8 10010010 0010010
输出 #1
NO YES YES NO YES NO
注意
在第一个测试用例中,您无法执行第一个操作。这样,你就输掉了比赛。
在第二个测试用例中,您可以在唯一操作中选择 $$$k=1$$$,之后 $$$s$$$ 就等于 $$$\mathtt{1}$$$。这样,你就赢得了比赛。
在第三个测试用例中,您可以执行以下操作: $$$\mathtt{1}\underline{\mathtt{10}}\mathtt{1}\xrightarrow{r_1=\mathtt{0}} \mathtt{1}\underline{\mathtt{01}} \xrightarrow{r_2=\mathtt{0}} \underline{\mathtt{10}} \xrightarrow{r_3=\mathtt{1}} \mathtt{1}$$$。