#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