#include <iostream>
//#include<alloc>
using namespace std;
int main()
{
int testcase;
cin>>testcase;
while(testcase--){
int length,flag=0,i;
cin>>length;
char *string;
string=(char *)malloc(sizeof(char)*length);
cin>>string;
for(i=0;i<length;i++){
if(string[i]=='H'||string[i]=='h')
flag=1;
if((string[i]=='T'||string[i]=='t')&&flag==0){
cout<<"Invalid"<<endl;
flag=2;
break;
}
if((string[i]=='T'||string[i]=='t')&&flag==1){
flag==0;
}
}
if(flag==1)
cout<<"Invalid"<<endl;
else if(flag==0)
cout<<"Valid"<<endl;
//cout<<string;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgovLyNpbmNsdWRlPGFsbG9jPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKQp7CiAgICBpbnQgdGVzdGNhc2U7CiAgICBjaW4+PnRlc3RjYXNlOwogICAgd2hpbGUodGVzdGNhc2UtLSl7CiAgICAgICAgaW50IGxlbmd0aCxmbGFnPTAsaTsKICAgICAgICBjaW4+Pmxlbmd0aDsKICAgICAgICBjaGFyICpzdHJpbmc7CiAgICAgICAgc3RyaW5nPShjaGFyICopbWFsbG9jKHNpemVvZihjaGFyKSpsZW5ndGgpOwogICAgICAgIGNpbj4+c3RyaW5nOwogICAgICAgIGZvcihpPTA7aTxsZW5ndGg7aSsrKXsKICAgICAgICAgICAgaWYoc3RyaW5nW2ldPT0nSCd8fHN0cmluZ1tpXT09J2gnKQogICAgICAgICAgICBmbGFnPTE7CiAgICAgICAgICAgIGlmKChzdHJpbmdbaV09PSdUJ3x8c3RyaW5nW2ldPT0ndCcpJiZmbGFnPT0wKXsKICAgICAgICAgICAgICAgIGNvdXQ8PCJJbnZhbGlkIjw8ZW5kbDsKICAgICAgICAgICAgICAgIGZsYWc9MjsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKChzdHJpbmdbaV09PSdUJ3x8c3RyaW5nW2ldPT0ndCcpJiZmbGFnPT0xKXsKICAgICAgICAgICAgICAgIGZsYWc9PTA7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgCiAgICAgICAgICAgIAogICAgICAgIH0KICAgICAgICBpZihmbGFnPT0xKQogICAgICAgIGNvdXQ8PCJJbnZhbGlkIjw8ZW5kbDsKICAgICAgICBlbHNlIGlmKGZsYWc9PTApCiAgICAgICAgY291dDw8IlZhbGlkIjw8ZW5kbDsKICAgICAgICAvL2NvdXQ8PHN0cmluZzsKICAgIH0KICAgIAogICAgcmV0dXJuIDA7Cn0K