← 返回题目列表

Codeforces · 1796/A

A. 典型面试问题

中文机器翻译题面 查看原题

FB 字符串的形成如下。最初,它是空的。我们从 $$$1$$$ 开始按升序遍历所有正整数,并对每个整数执行以下操作:

- 如果当前整数可被 $$$3$$$ 整除,则将 F 附加到 FB 字符串的末尾;
- 如果当前整数可被 $$$5$$$ 整除,则将 B 附加到 FB 字符串的末尾。

请注意,如果一个整数可被 $$$3$$$ 和 $$$5$$$ 整除,我们先附加 F,然后附加 B,而不是以相反的顺序。

FB 字符串的前 $$$10$$$ 字符是 FBFFBFFBFB:第一个 F 来自整数 $$$3$$$,下一个字符 (B) 来自 $$$5$$$,下一个 F 来自整数 $$$6$$$,依此类推。很容易看出这个字符串是无限长的。令 $$$f_i$$$ 为 FB 字符串的第 $$$i$$$ 个字符;因此,$$$f_1$$$ 是 F,$$$f_2$$$ 是 B,$$$f_3$$$ 是 F,$$$f_4$$$ 是 F,依此类推。

给定一个字符串 $$$s$$$,由字符 F 和/或 B 组成。您必须确定它是否是 FB 字符串的子字符串(连续子序列)。换句话说,确定是否可以选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r$$$) 使得字符串 $$$f_l f_{l+1} f_{l+2} \dots f_r$$$ 恰好是 $$$s$$$。

例如:

- FFB 是 FB 字符串的子字符串:如果我们选择 $$$l = 3$$$ 且 $$$r = 5$$$,则字符串 $$$f_3 f_4 f_5$$$ 正是 FFB;
- BFFBFFBF 是 FB 字符串的子字符串:如果我们选择 $$$l = 2$$$ 且 $$$r = 9$$$,则字符串 $$$f_2 f_3 f_4 \dots f_9$$$ 正是 BFFBFFBF;
- BBB 不是 FB 字符串的子字符串。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2046$$$) — 测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $$$k$$$ ($$$1 \le k \le 10$$$) — $$$s$$$ 中的字符数。第二行包含 $$$s$$$,它是一个恰好包含 $$$k$$$ 个字符的字符串。 $$$s$$$ 的每个字符都是 F 或 B。

输出

对于每个测试用例,如果 $$$s$$$ 是 FB 字符串的子字符串,则打印 YES,否则打印 NO。

您可以在任何情况下打印每个字母(YES、yes、Yes 都将被识别为肯定答案,NO、no 和 nO 都将被识别为否定答案)。

示例

输入 #1

3
3
FFB
8
BFFBFFBF
3
BBB

输出 #1

YES
YES
NO