#11167. A. Typical Interview Problem典型的面试问题

A. Typical Interview Problem典型的面试问题

题目:典型的面试问题

每个测试的时间限制: 2 秒 ⏳ 内存限制: 512 兆字节 💾

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

  • 如果当前整数可以被3整除,则在FB字符串的末尾附加F;
  • 如果当前整数可以被5整除,则在FB字符串的末尾附加B。

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

FB字符串的前10个字符是FBFFBFFBFB:第一个F来自整数3,下一个字符(B)来自整数5,下一个F来自整数6,依此类推。很容易看出这个字符串是无限长的。设fi是FB字符串的第i个字符;因此,f1是F,f2是B,f3是F,f4是F,以此类推。

给定一个由字符F和/或B组成的字符串s。你必须确定它是否是FB字符串的一个子串(连续子序列)。换句话说,确定是否可以选择两个整数l和r(1≤l≤r),使得字符串flfl+1fl+2…fr正好是s。

例如:

  • FFB是FB字符串的一个子串:如果我们选择l=3和r=5,字符串f3f4f5正好是FFB;
  • BFFBFFBF是FB字符串的一个子串:如果我们选择l=2和r=9,字符串f2f3f4…f9正好是BFFBFFBF;
  • BBB不是FB字符串的一个子串。

输入

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

每个测试用例包含两行。第一行包含一个整数k(1≤k≤10)——字符串s的字符数。第二行包含字符串s,正好有k个字符。s的每个字符都是F或B。


输出

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

你可以用任意大小写输出。例如,字符串 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。


示例

输入

3
3
FFB
8
BFFBFFBF
3
BBB

输出

YES
YES
NO