The annual snake festival is upon us, and all the snakes of the kingdom have gathered to participate in the procession. Chef has been tasked with reporting on the procession, and for this he decides to first keep track of all the snakes. When he sees a snake first, it'll be its Head, and hence he will mark a 'H'. The snakes are long, and when he sees the snake finally slither away, he'll mark a 'T' to denote its tail. In the time in between, when the snake is moving past him, or the time between one snake and the next snake, he marks with '.'s.
Because the snakes come in a procession, and one by one, a valid report would be something like "..H..T...HTH....T.", or "...", or "HT", whereas "T...H..H.T", "H..T..H", "H..H..T..T" would be invalid reports (See explanations at the bottom).
Formally, a snake is represented by a 'H' followed by some (possibly zero) '.'s, and then a 'T'. A valid report is one such that it begins with a (possibly zero length) string of '.'s, and then some (possibly zero) snakes between which there can be some '.'s, and then finally ends with some (possibly zero) '.'s.

Chef had binged on the festival food and had been very drowsy. So his report might be invalid. You need to help him find out if his report is valid or not.

-----Input-----
- The first line contains a single integer, R, which denotes the number of reports to be checked. The description of each report follows after this.
- The first line of each report contains a single integer, L, the length of that report.
- The second line of each report contains a string of length L. The string contains only the characters '.', 'H', and 'T'.

-----Output-----
- For each report, output the string "Valid" or "Invalid" in a new line, depending on whether it was a valid report or not.

-----Constraints-----
- 1 ≤ R ≤ 500
- 1 ≤ length of each report ≤ 500

-----Example-----
Input:
6
18
..H..T...HTH....T.
3
...
10
H..H..T..T
2
HT
11
.T...H..H.T
7
H..T..H

Output:
Valid
Valid
Invalid
Valid
Invalid
Invalid

-----Explanation-----
"H..H..T..T" is invalid because the second snake starts before the first snake ends, which is not allowed.
".T...H..H.T" is invalid because it has a 'T' before a 'H'. A tail can come only after its head.
"H..T..H" is invalid because the last 'H' does not have a corresponding 'T'.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
t=int(input())
for i in range(t):
 n=int(input())
 s=input().strip()
 c=0
 for i in range(len(s)):
  if s[i]=='.':
   continue
  if s[i]=='H':
   c+=1
  if s[i]=='T':
   c-=1
  if c>1:
   break
  if c<0:
   break
 if c==0:
  print('Valid')
 else:
  print('Invalid')

for i in range(int(input())):
 s = input()
 l = list(input())
 l = list([x for x in l if x != '.'])
 if 'T' in l[::2] or 'H' in l[1::2] or len(l)%2 != 0:
  print('Invalid')
 else:
  print('Valid')


# cook your dish here
for _ in range(int(input())):
 l = input()
 s = list(input())
 s = list([x for x in s if x != '.'])
 if 'T' in s[::2] or 'H' in s[1::2] or len(s)%2 != 0:
  print('Invalid')
 else:
  print('Valid')


t=int(input())
for i in range(t):
 n=int(input())
 s=input()
 c=0
 for i in s:
  if i=='H':
   c=c+1
  if i=='T':
   c=c-1
  if c>1:
   break
  if c<0:
   break
 if c==0:
  print('Valid')
 else:
  print('Invalid')

t=int(input())
for i in range(t):
 n=int(input())
 s=input()
 c=0
 for i in s:
  if i=='H':
   c=c+1
  if i=='T':
   c=c-1
  if c>1:
   break
  if c<0:
   break
 if c==0:
  print('Valid')
 else:
  print('Invalid')# cook your dish here


# cook your dish here
# cook your dish here
for z in range(int(input())) :
 n = int(input())
 s = input()
 s = s.replace('.','')
 l = len(s)
 if l%2 != 0 :
  print("Invalid")
 elif l==0 :
  print("Valid")
 elif s[0]!= 'H' or s[-1]!= 'T' :
  print("Invalid")
 else:
  for i in range(l-1):
   if s[i] == s[i+1] :
    print("Invalid")
    break
  else:
   print("Valid")

# cook your dish here
for z in range(int(input())) :
 n = int(input())
 s = input()
 s = s.replace('.','')
 l = len(s)
 if l%2 != 0 :
  print("Invalid")
 elif l==0 :
  print("Valid")
 elif s[0]!= 'H' or s[-1]!= 'T' :
  print("Invalid")
 else:
  for i in range(l-1):
   if s[i] == s[i+1] :
    print("Invalid")
    break
  else:
   print("Valid")

for _ in range(int(input())):
 
 n = int(input())
 
 s = input()
 
 h,t,prev,flag = 0,0,'',0
 
 for i in s:
  
  if prev == '' and i == 'T':
   
   flag = 1
  
  if i == 'H':
   
   h += 1
   
   if prev == 'H':
    
    flag = 1
   
  elif i == 'T':
   
   t += 1
   
   if prev == 'T':
    
    flag = 1
    
  if i in ('H','T'):
   
   prev = i
   
 print("Invalid" if flag == 1 else "Invalid" if h != t else "Valid")

t = int(input())
for z in range(t) :
 n = int(input())
 s = input()
 s = s.replace('.','')
 l = len(s)
 if l%2 != 0 :
  print("Invalid")
 elif l==0 :
  print("Valid")
 elif s[0]!= 'H' or s[-1]!= 'T' :
  print("Invalid")
 else:
  for i in range(l-1):
   if s[i] == s[i+1] :
    print("Invalid")
    break
  else:
   print("Valid")

t = int(input())
for i in range(t):
 n = int(input())
 a = input()
 valid = True
 count = 0
 for j in a:
  if j == 'H':
   count+=1
   if count>1:
    valid= False
  if j == 'T':
   count-=1
   if count<0:
    valid= False
 if valid and count==0:
  print('Valid')
 else:
  print('Invalid')


t = int(input())
for z in range(t) :
 n = int(input())
 s = input()
 s = s.replace('.','')
 l = len(s)
 if l%2 != 0 :
  print("Invalid")
 elif l==0 :
  print("Valid")
 elif s[0]!= 'H' or s[-1]!= 'T' :
  print("Invalid")
 else:
  for i in range(l-1):
   if s[i] == s[i+1] :
    print("Invalid")
    break
  else:
   print("Valid")

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=input()
 k="T"
 h=t=0
 f=0
 for i in range(n):
  if(l[i]=="H"):
   if(k=="T"):
    h+=1
    k="H"
   else:
    print("Invalid")
    f=1
    break
  elif(l[i]=="T"):
   if(k=="H"):
    t+=1
    k="T"
   else:
    print("Invalid")
    f=1
    break
 if(f==0):
  if(h!=t):
   print("Invalid")
  else:
   print("Valid")


# cook your dish here
t = int(input())
for z in range(t) :
 n = int(input())
 s = input()
 s = s.replace('.','')
 l = len(s)
 if l%2 != 0 :
  print("Invalid")
 elif l==0 :
  print("Valid")
 elif s[0]!= 'H' or s[-1]!= 'T' :
  print("Invalid")
 else:
  for i in range(l-1):
   if s[i] == s[i+1] :
    print("Invalid")
    break
  else:
   print("Valid")

t=int(input())
for i in range(t):
 s=[]
 b=[]
 c=0
 n=int(input())
 s=input()
 for j in s:
  if(j!="."):
   b.append(j)
 if(len(b)==0):
  print("Valid")
 elif(len(b)%2!=0):
  print("Invalid")
 elif(b[0]!='H' or b[-1]!='T'):
  print("Invalid")
 else:
  for j in range(len(b)-2):
   if(b[j]!=b[j+2]):
    c=1
    break
  if(c==0):
   print("Valid")
  else:
   print("Invalid")


# cook your dish here
for _ in range(int(input())):
 n=int(input())
 s=input()
 flag=0
 m='0'
 l=list(s)
 for i in s:
  if(i=='.'):
   l.remove(i)
 k=len(l)
 if(k==0):
  print("Valid")
 else:
  for i in range(0,k):
   if(l[0]=='T'):
    flag=1
    break
   if((l[i]=='H' and m=='H') or (l[i]=='T' and m=='T')):
    flag=1
    break
   if(l[i]=='H'):
    m='H'
   if(l[i]=='T'):
    m='T'
  if(flag==0 and l[k-1]=='T'):
   print('Valid')
  else:
   print('Invalid')


# cook your dish here
for i in range(int(input())):
 x=int(input())
 y=input()
 z=y.replace('.','')
 z=z.replace('HT','')
 print("Invalid" if len(z)>0 else "Valid")

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 a=input()
 b=[]
 c=0
 for i in a:
  if i=="H" or i=="T":
   b.append(i)
 while len(b)> 2*c:
  if len(b)%2!=0:
   print("Invalid")
   break
  elif b[2*c]=="H" and b[2*c +1]=="T":
   c=c+1 
  else:
   print("Invalid")
   break
 if 2*c==len(b):
  print("Valid")
 


R = int(input())
for i in range(R) :
 
 l = int(input())
 s = input()
 b = 0
 a = []
 for j in s :
  if j == "H" or j == "T" :
   a.append(j) 
 #List gets completed.
 while len(a) > 2*b :
  if len(a) % 2 != 0 :
   print("Invalid")
   break 

  elif a[2*b] == "H" and a[2*b + 1] == "T" :
   b = b + 1

  else :
   print("Invalid")
   break

 if 2*b == len(a) :
  print("Valid")









t=int(input())
while t:
 t-=1
 l=int(input())
 s=list(input())
 l=[]
 a=0
 for i in range(len(s)):
  if s[i]!='.':
   l.append(s[i])
   
 for i in range(0,len(l)-1,2):
  if l[i]=='H' and l[i+1]=='T':
   a+=2
 
 if(a==len(l)):
  print("Valid")
 else:
  print("Invalid")

for _ in range(int(input())):
 n=int(input())
 s=input()
 s=s.replace(".","")
 if len(s)==0:
  print( "Valid")
  continue
 elif len(s)==1 or s[len(s)-1]=='H' :
  print( "Invalid")
  continue
 for i in range(len(s)):
  if s[i]=="T" and i==0:
   print( "Invalid")
   break
  elif s[i]=='H':
   if s[i-1]=='H':
    print( "Invalid")
    break
  elif s[i]=='T':
   if s[i-1]=='T':
    print( "Invalid")
    break
 else:
  print( "Valid")

# cook your dish here

def answerFunction(s, n):
 prev = None
 new = ""
 for each in s:
  if each != '.':
   new += each
 if new == "":
  return "Valid"
 
 if len(new) == 1:
  return "Invalid"
 
 for i in range(len(new)): # HTHT
  if i == 0 and new[i] == 'T':
   return "Invalid"
  if new[i] == 'H':
   if prev == 'H':
    return "Invalid"
   else:
    prev = new[i]
  elif new[i] == 'T':
   if prev == 'T':
    return "Invalid"
   else:
    prev = new[i]
 if prev == 'H':
  return "Invalid"
 return "Valid";

for _ in range(int(input())):
 n = int(input())
 s = input()
 print(answerFunction(s, n))


# cook your dish here

def answerFunction(s, n):
 prev = None
 new = ""
 for each in s:
  if each != '.':
   new += each
 if new == "":
  return "Valid"
 
 if len(new) == 1:
  return "Invalid"
 
 for i in range(len(new)): # HTHT
  if i == 0 and new[i] == 'T':
   return "Invalid"
  if new[i] == 'H':
   if prev == 'H':
    return "Invalid"
   else:
    prev = new[i]
  elif new[i] == 'T':
   if prev == 'T':
    return "Invalid"
   else:
    prev = new[i]
 if prev == 'H':
  return "Invalid"
 return "Valid";

for _ in range(int(input())):
 n = int(input())
 s = input()
 print(answerFunction(s, n))


# cook your dish here
for _ in range(int(input())):
 n = int(input())
 s = input()
 l = []
 f = True
 for i in range(n):
  if s[i] == "H":
   l.append(s[i])
  elif s[i] == "T":
   if len(l)>=1:
    l = l[:-1]
   else:
    f = False
  if len(l)>1:
   f = False
 if len(l)>0:
  f = False
 if f == True:
  print("Valid")
 else:
  print("Invalid")

for _ in range(int(input())):
 n=int(input())
 s=list(input())
 if s.count('H')==s.count('T'):
  l=[]
  i=0
  while i<n:
   if s[i]!='.':
    l.append(s[i])
   i=i+1
  c=0
  for i in range(len(l)//2):
   if l[2*i]=="H" and l[(2*i)+1]=="T":
    c+=2
  if c==len(l):
   print("Valid")
  else:
   print("Invalid")
 else:
  print("Invalid")