A15676 | Typical Interview Problem

The FB-string is formed as follows. Initially, it is empty. We go through all positive integers, starting from $1$ , in ascending order, and do the following for each integer:

- if the current integer is divisible by $3$ , append F to the end of the FB-string;
- if the current integer is divisible by $5$ , append B to the end of the FB-string.

Note that if an integer is divisible by both $3$ and $5$ , we append F, and then B, not in the opposite order.

The first $10$ characters of the FB-string are FBFFBFFBFB: the first F comes from the integer $3$ , the next character (B) comes from $5$ , the next F comes from the integer $6$ , and so on. It's easy to see that this string is infinitely long. Let $f_i$ be the $i$ -th character of FB-string; so, $f_1$ is F, $f_2$ is B, $f_3$ is F, $f_4$ is F, and so on.

You are given a string $s$ , consisting of characters F and/or B. You have to determine whether it is a substring (contiguous subsequence) of the FB-string. In other words, determine if it is possible to choose two integers $l$ and $r$ ( $1 \le l \le r$ ) so that the string $f_l f_{l+1} f_{l+2} \dots f_r$ is exactly $s$ .

For example:

- FFB is a substring of the FB-string: if we pick $l = 3$ and $r = 5$ , the string $f_3 f_4 f_5$ is exactly FFB;
- BFFBFFBF is a substring of the FB-string: if we pick $l = 2$ and $r = 9$ , the string $f_2 f_3 f_4 \dots f_9$ is exactly BFFBFFBF;
- BBB is not a substring of the FB-string.

The first line contains one integer $t$ ( $1 \le t \le 2046$ ) — the number of test cases.

Each test case consists of two lines. The first line contains one integer $k$ ( $1 \le k \le 10$ ) — the number of characters in $s$ . The second line contains $s$ , which is a string of exactly $k$ characters. Each character of $s$ is either F or B.

For each test case, print YES if $s$ is a substring of the FB-string, or NO otherwise.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).