B. pspspspstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output Cats are attracted to pspspsps, but Evirir, being a dignified dragon, is only attracted to pspspsps with oddly specific requirements...Given a string $$$s = s_1s_2\ldots s_n$$$ of length $$$n$$$ consisting of characters p, s, and . (dot), determine whether a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$ exists, such that for all integers $$$i$$$ ($$$1 \le i \le n$$$): If $$$s_i$$$ is p, then $$$[p_1, p_2, \ldots, p_i]$$$ forms a permutation (of length $$$i$$$); If $$$s_i$$$ is s, then $$$[p_i, p_{i+1}, \ldots, p_{n}]$$$ forms a permutation (of length $$$n-i+1$$$); If $$$s_i$$$ is ., then there is no additional restriction. $$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array). InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 500$$$), the length of $$$s$$$.The second line of each test case contains a string $$$s$$$ of length $$$n$$$ that consists of the characters p, s, and ..It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$. OutputFor each test case, output YES or NO on a line. Output YES if there is such a permutation and NO otherwise.You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.ExampleInput94s.sp6pss..s5ppppp2sp4.sp.8psss....1.8pspspsps20....................OutputYES
NO
YES
YES
NO
NO
YES
NO
YES
NoteFor the first test case, one permutation that works is $$$p = [3, 4, 1, 2]$$$. The restrictions are as follows: $$$s_1 =$$$ s: $$$[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$$$ forms a permutation. $$$s_2 =$$$ .: No additional restriction. $$$s_3 =$$$ s: $$$[p_3, p_4] = [1, 2]$$$ forms a permutation. $$$s_4 =$$$ p: $$$[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$$$ forms a permutation. For the second test case, it can be proven that there is no permutation that satisfies all restrictions.For the third test case, one permutation that satisfies the constraints is $$$p = [1, 2, 3, 4, 5]$$$.