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: EASY
Tags: String algorithms

Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
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())
	snack = input()
	prev = 'T'
	flag = 0
	for i in snack:
		if i == '.':
			continue
		elif i != prev:
			prev = i
		else:
			flag = 1
			break
	if flag == 0 and prev == 'T':
		print('Valid')
	else:
		print('Invalid')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l = []
	for j in s:
		if j == 'H' or j == 'T':
			l.append(j)
	l = ''.join(l)
	h = l.count('H')
	t = l.count('T')
	hh = l.count('HH')
	ht = l.count('HT')
	if h != t or hh > 0 or ht < len(l) // 2:
		print('Invalid')
	else:
		print('Valid')


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')


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	l = []
	for i in s:
		if i == 'H':
			if len(l) == 0:
				l.append(i)
			else:
				break
		elif i == 'T':
			if len(l) != 0:
				l.pop()
			else:
				l.append(i)
				break
	if len(l) == 0:
		print('Valid')
	else:
		print('Invalid')


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)):
		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))


for _ in range(int(input())):
	l = int(input())
	s = input()
	l = l - s.count('.')
	s = s.replace('.', '')
	if s == '' or (s[0] == 'H' and s[l - 1] == 'T' and ('HH' not in s) and ('TT' not in s)):
		print('Valid')
	else:
		print('Invalid')


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')


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')


n = int(input())
for i in range(1, n + 1):
	a = int(input())
	b = input()
	c = b.count('H')
	d = b.count('T')
	e = []
	for i in b:
		if i == 'H' or i == 'T':
			e.append(i)
	if len(e) == 0:
		print('Valid')
	elif len(e) % 2 == 0:
		for i in range(len(e)):
			if i % 2 == 0 and e[i] != 'H':
				print('Invalid')
				break
			if i % 2 == 1 and e[i] != 'T':
				print('Invalid')
				break
		else:
			print('Valid')
	else:
		print('Invalid')


R = int(input())
for j in range(R):
	L = int(input())
	s = input()
	st = []
	flag = True
	for i in s:
		if i == 'H':
			if len(st) == 0:
				flag = True
				st.append('H')
			elif st[-1] == 'H':
				flag = False
				print('Invalid')
				break
		elif i == 'T':
			if len(st) == 0:
				flag = False
				print('Invalid')
				break
			elif st[-1] == 'T':
				flag = False
				print('Invalid')
				break
			elif st[-1] == 'H':
				flag = True
				st.pop()
	if len(st) == 0 and flag:
		print('Valid')
	elif flag:
		print('Invalid')


for _ in range(int(input())):
	A = int(input())
	B = input()
	X = 0
	for i in B:
		if i == 'H':
			X += 1
		if i == 'T':
			X -= 1
		if X < 0 or X > 1:
			print('Invalid')
			break
	else:
		if X == 0:
			print('Valid')
		else:
			print('Invalid')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if 'H' not in s and 'T' not in s:
		print('Valid')
	else:
		l = []
		c = 0
		for j in s:
			if j == 'H' or j == 'T':
				l.append(j)
		if l.count('H') != l.count('T'):
			print('Invalid')
		else:
			for k in range(0, len(l), 2):
				if l[k] == 'H' and l[k + 1] == 'T':
					c += 2
			if c == len(l):
				print('Valid')
			else:
				print('Invalid')


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')


for i in range(int(input())):
	l = int(input())
	s = input()
	box = []
	c = 0
	for j in range(l):
		if s[j] == 'H' or s[j] == 'T':
			box.append(s[j])
	blen = len(box)
	if blen == 0:
		print('Valid')
	elif blen > 0:
		if box[0] != 'H' or box[blen - 1] != 'T':
			print('Invalid')
		else:
			for k in range(blen):
				if k % 2 == 0:
					if box[k] == 'H':
						c = 1
					else:
						c = 0
						break
				if k % 2 != 0:
					if box[k] == 'T':
						c = 1
					else:
						c = 0
						break
			if c == 1:
				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')


for i in range(int(input())):
	num = int(input())
	inp = input().replace('.', '')
	if inp.count('H') == inp.count('T'):
		if 'HH' in inp or 'TT' in inp:
			print('Invalid')
		elif inp.startswith('T'):
			print('Invalid')
		else:
			print('Valid')
	else:
		print('Invalid')


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 r in range(int(input())):
	l = int(input())
	rep = input()
	rep_l = [r for r in rep if r == 'H' or r == 'T']
	rep_s = ''.join(rep_l)
	count = rep_s.count('HT', 0, len(rep_s))
	if count == len(rep_s) / 2:
		print('Valid')
	else:
		print('Invalid')


t = int(input())
for i in range(t):
	r = int(input())
	l = input()
	new = []
	for i in l:
		if i == 'H' or i == 'T':
			new.append(i)
	if len(new) % 2 == 0:
		f = 0
		for i in range(0, len(new) - 1, 2):
			if new[i] == 'H' and new[i + 1] == 'T':
				continue
			else:
				f = 1
				break
		if f == 1:
			print('Invalid')
		else:
			print('Valid')
	else:
		print('Invalid')


r = int(input())
for i in range(r):
	n = int(input())
	l = input()
	check = 0
	l1 = list(l)
	l2 = []
	for j in l1:
		if j == 'H' or j == 'T':
			l2.append(j)
	for k in range(0, len(l2) - 1, 2):
		if l2[k] == 'T' or l2[k + 1] == 'H':
			check = 1
	if l.count('T') != l.count('H'):
		check = 1
	if check == 1:
		print('Invalid')
	else:
		print('Valid')


t = int(input())
while t > 0:
	b = 0
	count = 0
	n = int(input())
	a = input()
	for i in range(n):
		if a[i] == 'H' and count == 0 and ('T' in a[i:]):
			count = 1
		elif a[i] == 'T' and count == 1:
			count = 0
		elif a[i] == '.':
			pass
		else:
			b = 1
	if b == 1:
		print('Invalid')
	else:
		print('Valid')
	t -= 1


t = int(input())
for x in range(t):
	n = int(input())
	s = input()
	a = []
	for i in s:
		if i == 'H' or i == 'T':
			a.append(i)
	if len(a) == 0:
		print('Valid')
	elif len(a) % 2 == 0:
		for j in range(len(a)):
			if j % 2 == 0 and a[j] != 'H':
				print('Invalid')
				break
			if j % 2 != 0 and a[j] != 'T':
				print('Invalid')
				break
		else:
			print('Valid')
	else:
		print('Invalid')


reports = input()
for r in range(int(reports)):
	_ = input()
	s = input()
	s = s.replace('.', '').replace('HT', '')
	print('Valid' if len(s) == 0 else 'Invalid')


r = int(input())
for tc in range(r):
	l = int(input())
	s = input()
	l1 = list(s)
	for _ in range(l1.count('.')):
		l1.remove('.')
	if len(l1) % 2 == 0:
		f = 0
		for i in range(0, len(l1) - 1, 2):
			if l1[i] == 'H' and l1[i + 1] == 'T':
				continue
			else:
				f = 1
				break
		if f == 1:
			print('Invalid')
		else:
			print('Valid')
	else:
		print('Invalid')


for _ in range(int(input())):
	(N, L) = (int(input()), input().split('H'))
	flag = L[0].count('T')
	for i in range(1, len(L)):
		if flag or L[i].count('T') != 1:
			flag = True
			break
	print('Invalid' if flag else 'Valid')


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')


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')


for _ in range(int(input())):
	a = int(input())
	c = input()
	h = 0
	t = 0
	b = False
	for i in c:
		if i == 'H':
			if h == 0:
				h = 1
			else:
				b = True
				break
		elif i == 'T':
			if h == 1:
				t = 1
				h = 0
			else:
				b = True
				break
	if b == True or h > 0:
		print('Invalid')
	else:
		print('Valid')


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')


for i in range(int(input())):
	n = int(input())
	s = input()
	if '.' not in s:
		if s.startswith('H') and s.endswith('T'):
			print('Valid')
		else:
			print('Invalid')
		continue
	s = s.strip('.')
	if s.count('H') != s.count('T'):
		print('Invalid')
	elif s.startswith('T') or s.endswith('H'):
		print('Invalid')
	elif 'HH' in s or 'TT' in s:
		print('Invalid')
	else:
		print('Valid')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	con = 0
	h = 0
	k = 0
	for j in range(n):
		if con == 0 and s[j] == 'H':
			con = 1
			h += 1
		elif con == 1 and s[j] == 'T':
			con = 0
			k += 1
		elif con == 0 and s[j] == 'T':
			con = 2
			break
		elif con == 1 and s[j] == 'H':
			con = 2
			break
	if con == 0:
		print('Valid')
	else:
		print('Invalid')


def rahul(n):
	n = n.replace('.', '')
	c = 0
	a = n.count('T')
	b = n.count('H')
	if a == b:
		d = n.count('HT')
		k = len(n) - 2 * d
		if k != 0:
			c += 1
	else:
		c += 1
	return c
s = int(input())
while s != 0:
	x = int(input())
	n = input()
	k = rahul(n)
	if k == 0:
		print('Valid')
	else:
		print('Invalid')
	s = s - 1


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	if s.count('H') != s.count('T'):
		print('Invalid')
	else:
		for i in s:
			if i == 'H':
				c += 1
				if c == 2:
					print('Invalid')
					break
			elif i == 'T':
				c -= 1
				if c < 0:
					print('Invalid')
					break
		if c == 0:
			print('Valid')


t = int(input())
for i in range(t):
	a = int(input())
	s = str(input())
	s = list(s)
	x = []
	y = ''
	count = 0
	for j in range(len(s)):
		if s[j] == '.':
			y += s[j]
		elif s[j] == 'H' and len(x) == 0:
			x.append(s[j])
		elif s[j] == 'T' and len(x) != 0 and (x[-1] == 'H'):
			x.pop()
			count += 2
		else:
			continue
	z = count + len(y)
	if len(x) == 0 and z == a:
		print('Valid')
	else:
		print('Invalid')


for _ in range(int(input())):
	l = int(input())
	s = input()
	s = s.replace('.', '')
	o = 'Valid'
	if len(s) == 1:
		o = 'Invalid'
	elif len(s) > 1:
		for i in range(len(s) - 1):
			if s == '':
				pass
			elif s[0] != 'H':
				o = 'Invalid'
			elif s[i] == s[i + 1]:
				o = 'Invalid'
			elif s.count('H') != s.count('T'):
				o = 'Invalid'
	print(o)


t = int(input())
for i in range(t):
	a = int(input())
	b = input()
	c = 0
	for j in range(a):
		if b[j] == 'H' and c == 0:
			c = 1
		elif b[j] == 'H' and c == 1:
			c = 2
		elif b[j] == 'T' and c == 1:
			c = 0
		elif b[j] == 'T' and c == 0:
			c = 2
		if b[j] == '.':
			pass
	if c == 2 or c == 1:
		print('Invalid')
	else:
		print('Valid')


x = int(input())
while x != 0:
	n = int(input())
	s = input()
	l = []
	for i in s:
		if i == 'H' or i == 'T':
			l.append(i)
	l = ''.join(l)
	if len(l) == 0:
		print('Valid')
	else:
		k = l.count('HT')
		if len(l) % 2 == 0:
			if k == len(l) // 2:
				print('Valid')
			else:
				print('Invalid')
		elif k == len(l) // 2 + 1:
			print('Valid')
		else:
			print('Invalid')
	x -= 1


for j in range(int(input())):
	N = int(input())
	S = input()
	L = []
	for j in S:
		if j == 'H' or j == 'T':
			L.append(j)
	L = ''.join(L)
	h = L.count('H')
	T = L.count('T')
	hh = L.count('HH')
	ht = L.count('HT')
	if h != T or hh > 0 or ht < len(L) // 2:
		print('Invalid')
	else:
		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)
	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())
for i in range(t):
	n = int(input())
	s = input()
	l = []
	for i in s:
		if i == '.':
			pass
		elif i == 'H' or i == 'T':
			l.append(i)
	if len(l) == 0:
		print('Valid')
	else:
		count1 = 0
		count2 = 0
		for i in range(len(l)):
			if l[i] == 'H' and i % 2 == 0:
				count1 += 1
			elif l[i] == 'T' and i % 2 == 1:
				count2 += 1
		if (count1 + count2) % 2 == 0 and len(l) == count1 + count2:
			print('Valid')
		else:
			print('Invalid')


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')


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')


t = int(input())
for j in range(t):
	l = []
	(h, t, a) = (0, 0, 0)
	n = int(input())
	s = input()
	for k in s:
		if k == '.':
			a += 1
	if a == n:
		print('Valid')
	else:
		for i in s:
			if i == 'H' or i == 'T':
				l.append(i)
		if len(l) % 2 != 0:
			print('Invalid')
		else:
			for i in range(len(l)):
				if i % 2 == 0 and l[i] == 'H':
					h += 1
				elif i % 2 != 0 and l[i] == 'T':
					t += 1
			if h == len(l) // 2 and t == len(l) // 2:
				print('Valid')
			else:
				print('Invalid')


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')


def is_valid_report(report):
	state = 0
	for char in report:
		if state == 0:
			if char == 'H':
				state = 1
			elif char != '.':
				return 'Invalid'
		elif state == 1:
			if char == 'T':
				state = 0
			elif char != '.':
				return 'Invalid'
	if state == 1:
		return 'Invalid'
	else:
		return 'Valid'
num_reports = int(input())
for i in range(num_reports):
	report_length = int(input())
	report_string = input()
	print(is_valid_report(report_string))


for _ in range(int(input())):
	n = int(input())
	l = ''.join(input().split('.'))
	if len(l) == 0:
		print('Valid')
	elif len(l) % 2 == 1:
		print('Invalid')
	else:
		flag = 1
		for i in range(len(l)):
			if i % 2 == 0 and l[i] == 'T':
				flag = 0
			if i % 2 == 1 and l[i] == 'H':
				flag = 0
		if flag == 0:
			print('Invalid')
		else:
			print('Valid')


for i in range(int(input())):
	n = int(input())
	q = input()
	l = []
	for i in q:
		if i == 'H' or i == 'T':
			l.append(i)
	l = ''.join(l)
	h = l.count('H')
	t = l.count('T')
	h2 = l.count('HH')
	t2 = l.count('HT')
	if h != t or h2 > 0 or t2 < len(l) // 2:
		print('Invalid')
	else:
		print('Valid')


for i in range(int(input())):
	n = int(input())
	s = input()
	k = []
	a = []
	for j in s:
		if j == 'H' or j == 'T':
			k.append(j)
	if k == a:
		print('Valid')
	elif k[0] == 'T':
		print('Invalid')
	elif k.count('H') != k.count('T'):
		print('Invalid')
	elif k.count('H') == k.count('T'):
		for j in range(len(k) - 1):
			if k[j] == k[j + 1]:
				print('Invalid')
				break
		else:
			print('Valid')
	else:
		print('Valid')


Reports = int(input())
for Report in range(Reports):
	LengthofReport = int(input())
	String = input()
	ReportResult = []
	for Alphabets in String:
		if Alphabets == 'H' or Alphabets == 'T':
			ReportResult.append(Alphabets)
	ReportResult = ''.join(ReportResult)
	HeadCount = ReportResult.count('H')
	TailCount = ReportResult.count('T')
	HeadHeadCount = ReportResult.count('HH')
	HeadTailCount = ReportResult.count('HT')
	if HeadCount != TailCount or HeadHeadCount > 0 or HeadTailCount < len(ReportResult) // 2:
		print('Invalid')
	else:
		print('Valid')


def isValid(n, snake):
	stack = []
	for i in snake:
		if i == 'H':
			if len(stack) != 0:
				return 'Invalid'
			stack.append('*')
		elif i == 'T':
			if len(stack) == 0:
				return 'Invalid'
			stack.pop()
	return 'Valid' if len(stack) == 0 else 'Invalid'
for _ in range(int(input())):
	n = int(input())
	snake = input()
	print(isValid(n, snake))


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	c = 0
	for i in range(n):
		if s[i] == 'H' and c == 0:
			c = 1
		elif s[i] == 'H' and c == 1:
			c = 2
		elif s[i] == 'T' and c == 1:
			c = 0
		elif s[i] == 'T' and c == 0:
			c = 2
	if c == 2 or c == 1:
		print('Invalid')
	else:
		print('Valid')
	t -= 1


def is_valid_report(report):
	num_h = 0
	in_snake = False
	for c in report:
		if c == 'H':
			if in_snake:
				return 'Invalid'
			num_h += 1
			in_snake = True
		elif c == 'T':
			if not in_snake or num_h == 0:
				return 'Invalid'
			num_h -= 1
			in_snake = False
		elif c != '.':
			return 'Invalid'
	if num_h != 0 or in_snake:
		return 'Invalid'
	return 'Valid'
num_reports = int(input())
for i in range(num_reports):
	report_length = int(input())
	report = input()
	print(is_valid_report(report))


for i in range(int(input())):
	n = int(input())
	k = input()
	s = ''
	for i in k:
		if i == 'H' or i == 'T':
			s += i
	if s.count('HT') == s.count('H') and s.count('H') == s.count('T'):
		print('Valid')
	else:
		print('Invalid')


for _ in range(int(input())):
	n = int(input())
	s = input()
	h1 = ''
	for i in range(n):
		if s[i] in ['H', 'T']:
			h1 += s[i]
	if len(h1) % 2 != 0:
		print('Invalid')
	else:
		for j in range(0, len(h1)):
			if j % 2 == 0:
				if h1[j] != 'H':
					print('Invalid')
					break
			elif h1[j] != 'T':
				print('Invalid')
				break
		else:
			print('Valid')


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')


for _ in range(int(input())):
	x = int(input())
	y = input()
	l = list(y)
	for _ in range(l.count('.')):
		l.remove('.')
	if len(l) % 2 == 0:
		k = 0
		for i in range(0, len(l) - 1, 2):
			if l[i] == 'H' and l[i + 1] == 'T':
				continue
			else:
				k = 1
				break
		if k == 1:
			print('Invalid')
		else:
			print('Valid')
	else:
		print('Invalid')


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	c = 0
	while i < n:
		if s[i] == 'H' and c == 0:
			c = 1
		elif s[i] == 'T' and c == 1:
			c = 0
		elif s[i] == '.':
			pass
		else:
			c = 1
			break
		i += 1
	if c == 1:
		print('Invalid')
	else:
		print('Valid')


for _ in range(int(input())):
	a = int(input())
	b = input()
	if b.count('H') != b.count('T'):
		print('Invalid')
	else:
		c = ''
		for i in b:
			if i == 'H' or i == 'T':
				c += i
		if c == '':
			print('Valid')
		elif c[0] == 'T' or (c.count('TT') > 0 or c.count('HH') > 0):
			print('Invalid')
		else:
			print('Valid')


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


n = int(input())
for k in range(n):
	lent = int(input())
	t = input()
	l = []
	for i in t:
		if i != '.':
			l.append(i)
	f = True
	c = 0
	for i in l:
		if i == 'H':
			c += 1
		if i == 'T':
			c -= 1
		if c != 1 and c != 0:
			f = False
			break
	if f and c == 0:
		print('Valid')
	else:
		print('Invalid')


R = int(input())
for _ in range(R):
	L = int(input())
	snakes_with_dots = input()
	snakes_wo_dots = snakes_with_dots.replace('.', '')
	snake_lst = list(snakes_wo_dots)
	if len(snake_lst) % 2 != 0:
		valid = False
	else:
		for i in range(len(snake_lst)):
			if i % 2 == 0:
				if snake_lst[i] == 'H':
					valid = True
				else:
					valid = False
					break
			elif snake_lst[i] == 'T':
				valid = True
			else:
				valid = False
				break
	if valid:
		print('Valid')
	else:
		print('Invalid')