Description

你需要解决一个与扑克游戏「斗地主」相关的问题。

游戏介绍

「斗地主」是一款三名玩家轮流出牌的游戏。三名玩家分别为 A、B、C。 每位玩家手中持有若干牌，游戏持续到有一名玩家出完所有手牌为止。

• 玩家 A 和 B 属于农民阵营：只要 A 或 B 任意一人出完所有手牌，农民获胜。
• 玩家 C 是地主阵营：若 C 出完所有手牌，地主获胜。

出牌规则

本题中，每张牌都有一个 $[1,n]$ 的数字，称为牌点数。点数大小顺序为：$1 < 2 < \dots < n$。

本题仅允许以下两种合法牌型：

• 单张：任意一张单独的牌。
• 对子：两张点数相同的牌。

与常规斗地主不同，本题中玩家只能在恰好拥有 1 张该点数牌时才能出单张，即手中的对子不可以拆分成两个单张打出。

每一轮游戏中，会有一名玩家作为本轮起始玩家先行行动，可以打出任意合法牌型。 随后按顺序轮到下一位玩家，每位玩家只能选择以下两种操作之一：

1. 打出与上一轮最后打出的牌型相同、且点数严格更大的牌型。
2. 选择不出（Pass）。

当一名玩家打出牌型后，若另外两名玩家连续都选择不出，则本轮结束。 本轮最后一次成功出牌的玩家，将成为下一轮的起始玩家，开启新的一轮。

问题描述

本题给定固定游戏局面：

• 地主 C 仅剩最后一张牌，点数为 $p_c$。
• 农民 A、B 的手牌由两个仅含 0、1、2 的字符串 $s_a$、$s_b$ 描述：第 $i$ 位字符表示该玩家拥有点数为 $i$ 的牌的数量。

所有玩家的手牌均为公共信息，所有人都知道彼此的牌。 玩家 A 是第一轮的起始玩家，出牌顺序固定为：$\boldsymbol{A \to B \to C \to A \to \dots}$。

假设所有玩家都采取最优策略，请你判断农民阵营是否必定能获胜。

Format

Input

多组测试用例。 第一行输入一个整数 $T\ (1 \le T \le 10^5)$，表示测试用例数量。

每组测试用例： 第一行输入一个整数 $n\ (1 \le n \le 2.5\times10^5)$。 第二行输入一个长度为 $n$、仅由 0/1/2 组成的字符串 $s_a$，表示农民 A 的手牌。 第三行输入一个长度为 $n$、仅由 0/1/2 组成的字符串 $s_b$，表示农民 B 的手牌。 第四行输入一个整数 $p_c\ (1 \le p_c \le n)$，表示地主 C 最后一张牌的点数。

保证每位玩家至少有一张牌； 保证所有测试用例的 $n$ 之和不超过 $10^6$。

Output

对于每组测试用例：

• 若农民阵营在最优策略下必胜，输出 Yes。
• 否则输出 No。

Samples

4
9
001110201
002110211
7
9
110200000
222000000
7
9
222000000
110000000
7
9
111000002
111000210
7

Yes
No
Yes
No

Limitation

1s, 1024KiB for each test case.