#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
 
int main(){
	int N,n;
	string s;
	cin>>N;
	while(N--){
		cin>>n>>s;
		s.erase(remove(s.begin(),s.end(),'.'),s.end());
		//cout<<s<<endl;
		if(s.length()==0){
			cout<<"valid"<<endl;
		}else if(s.length() ==1 || s.length()%2 !=0){
			cout<<"invalid"<<endl;
		}
		else{
			for(int i=0; i<s.length()-1; i++){
				if(s[i]=='H' && s[i+1] == 'T'){
					i+=2;
				}else{
					cout<<"invalid"<<endl;
					i=s.length();
				}
			}
			cout<<"valid"<<endl;
		}
	}
	return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgppbnQgbWFpbigpewoJaW50IE4sbjsKCXN0cmluZyBzOwoJY2luPj5OOwoJd2hpbGUoTi0tKXsKCQljaW4+Pm4+PnM7CgkJcy5lcmFzZShyZW1vdmUocy5iZWdpbigpLHMuZW5kKCksJy4nKSxzLmVuZCgpKTsKCQkvL2NvdXQ8PHM8PGVuZGw7CgkJaWYocy5sZW5ndGgoKT09MCl7CgkJCWNvdXQ8PCJ2YWxpZCI8PGVuZGw7CgkJfWVsc2UgaWYocy5sZW5ndGgoKSA9PTEgfHwgcy5sZW5ndGgoKSUyICE9MCl7CgkJCWNvdXQ8PCJpbnZhbGlkIjw8ZW5kbDsKCQl9CgkJZWxzZXsKCQkJZm9yKGludCBpPTA7IGk8cy5sZW5ndGgoKS0xOyBpKyspewoJCQkJaWYoc1tpXT09J0gnICYmIHNbaSsxXSA9PSAnVCcpewoJCQkJCWkrPTI7CgkJCQl9ZWxzZXsKCQkJCQljb3V0PDwiaW52YWxpZCI8PGVuZGw7CgkJCQkJaT1zLmxlbmd0aCgpOwoJCQkJfQoJCQl9CgkJCWNvdXQ8PCJ2YWxpZCI8PGVuZGw7CgkJfQoJfQoJcmV0dXJuIDA7Cn0K

NgoxOAouLkguLlQuLi5IVEguLi4uVC4KMwouLi4KMTAKSC4uSC4uVC4uVAoyCkhUCjExCi5ULi4uSC4uSC5UCjcKSC4uVC4uSA==

6
18
..H..T...HTH....T.
3
...
10
H..H..T..T
2
HT
11
.T...H..H.T
7
H..T..H