There is a Band Procession which requires singer S to stand first and
the pianist P to stand at last.
The Band Procession can be represented as ‘S.P’ (there can be any
number of ‘.’).
The bands come in procession, but one by one. A valid procession
will be ‘S….P’ or ‘S…P’ or ‘S…P…S……P’ whereas ‘S.P.S’ or
‘S.S….P…S’ are invalid.
You are given task to identify whether a Band Procession is Valid or
- The first line contains a single integer, T, which denotes the
number of test cases to be checked. The description of each test
case follows this.
- The first line of each report contains a single integerL which
indicates the length of that report.
- The second line of each report contains a string of length L. The
string contains only the characters ‘.’, ‘S’, and ‘P’.
- For each test case, output the string Valid or Invalid in a new line,
depending on whether it was a valid Band Procession or not.
Sample Test Case:
Test Case 1: “S…S…P…P” is invalid because the second Band
starts before the first Band ends, which is not allowed.
• Test Case 2: “.P…S…S.P” is invalid because it has a ‘P’ before a
‘S’. A Pianist can come only after its Band’s Singer.
• Test Case 3: “S…P…S” is invalid because the last ‘S’ does not have
a corresponding ‘P’.
for __ in range(int(input())): N = int(input()) S = input().replace('.', '') if S.count('S') != S.count('P') or S.replace('SP', '') != '': print('Invalid') else: print('Valid')