CF1796A 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).