猫会被 pspspsps 所吸引,但埃维里尔,作为一条高贵的龙,只会被具有奇怪的特定要求的 pspspsps 所吸引......
给定一个字符串 $$$s = s_1s_2\ldots s_n$$$,长度为 $$$n$$$,由字符 p、s 和 组成。 (点),确定是否存在长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$,使得对于所有整数 $$$i$$$ ($$$1 \le i \le n$$$):
- 如果 $$$s_i$$$ 是 p,则 $$$[p_1, p_2, \ldots, p_i]$$$ 形成一个排列(长度为 $$$i$$$);
- 如果 $$$s_i$$$ 是 s,则 $$$[p_i, p_{i+1}, \ldots, p_{n}]$$$ 形成一个排列(长度为 $$$n-i+1$$$);
- 如果 $$$s_i$$$ 是 .,则没有附加限制。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数$$$n$$$ ($$$1 \le n \le 500$$$),长度为$$$s$$$。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 p、s 和 .. 组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,在一行上输出 YES 或 NO。如果存在这样的排列则输出 YES,否则输出 NO。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
9 4 s.sp 6 pss..s 5 ppppp 2 sp 4 .sp. 8 psss.... 1 . 8 pspspsps 20 ....................
输出 #1
YES NO YES YES NO NO YES NO YES
注意
对于第一个测试用例,有效的排列是 $$$p = [3, 4, 1, 2]$$$。限制如下:
- $$$s_1 =$$$ s: $$$[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$$$ 形成排列。
- $$$s_2 =$$$ .:无附加限制。
- $$$s_3 =$$$ s: $$$[p_3, p_4] = [1, 2]$$$ 形成排列。
- $$$s_4 =$$$ p: $$$[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$$$ 形成排列。
对于第二个测试用例,可以证明不存在满足所有限制的排列。
对于第三个测试用例,满足约束的一种排列是 $$$p = [1, 2, 3, 4, 5]$$$。