有一个长度为 $$$n$$$ 的字符串 $$$T$$$,使得 $$$T_i=$$$ 'a' 对于所有奇数 $$$i$$$ 和 $$$T_i=$$$ 'b' 对于所有 $$$i$$$。
有一天,Bob 使用以下算法生成了一个字符串 $$$S$$$。
- 将 $$$S$$$ 初始化为空字符串。
- 删除 第一 信函或 最后 来自 $$$T$$$ 的信,以及 追加 到$$$S$$$。
- 如果 $$$T$$$ 为空,则终止并返回字符串 $$$S$$$。否则,返回第二步。
然后,Bob 将生成的字符串 $$$S$$$ 写在便条上,并在几年后忘记了它。当鲍勃发现这张纸条时,它已经磨损了,有人可能偷偷地更改了一些字母。当然,鲍勃想知道是否有人更改了字符串!
给定一个长度为 $$$n$$$ 的字符串 $$$X$$$,其中包含 'a', 'b', 和 '?'.
请判断是否存在满足以下条件的字符串$$$A$$$:
- $$$|A|=n$$$;
- $$$A_i$$$ 是 'a' 或 'b' 对于所有 $$$1 \le i \le n$$$;
- $$$A_i=X_i$$$ 对于所有 $$$1 \le i \le n$$$ 使得 $$$X_i$$$ 不是 '?';
- 字符串 $$$A$$$ 可以通过上述算法生成。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$)。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$X$$$,由 'a', 'b', 和 '?'.
保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。
输出
如果存在满足所有条件的字符串$$$A$$$,则输出“是" 在单独的一行上。
如果有 没有 满足所有条件的字符串$$$A$$$,输出“NO" 在单独的一行上。
任何情况下都可以输出答案。例如,字符串“是", "是的", "是”也将被视为积极响应。
示例
输入复制
45ababa5baaba5?b?ab6aa?b?b
输出复制
YESNOYESNO
注意
对于第二个测试用例,字符串“粑粑" 不能 由上述算法生成。
对于第三个测试用例,字符串“abaab”可以通过上述算法生成:
- 最初,$$$T$$$ 是“贝巴" 且 $$$S$$$ 为空。
- 删除 $$$T$$$ 中的第一个字母。 $$$T$$$ 变为“粑粑" 和 $$$S$$$ 变为 "a".
- 删除 $$$T$$$ 中的第一个字母。 $$$T$$$ 变为“阿巴" 和 $$$S$$$ 变为 "ab".
- 删除 $$$T$$$ 中的最后一个字母。 $$$T$$$ 变为“ab" 和 $$$S$$$ 变为 "阿巴".
- 删除 $$$T$$$ 中的第一个字母。 $$$T$$$ 变为“b" 和 $$$S$$$ 变为 "abaa".
- 删除 $$$T$$$ 中的最后一个字母。 $$$T$$$ 变为空,$$$S$$$ 变为 "abaab".