/* package whatever; // don't place package name! */
#include <iostream>
int main()
{
int testcase,nlines,i;
std::cin>>testcase;
int res[testcase];
char result[2][8]={"Valid","Invalid"};
for(i=0;i<testcase;i++){
int count=0,h=0,b=0,t=0;
std::cin>>nlines;
char a[nlines];
std::cin>>a;
for(int j=0;j<nlines;j++){
switch(a[j]){
case 'H':
if(b==0){
count++;
b=1;
h++;
break;
}
else{
goto endloop;
}
case '.':
count++;
break;
case 'T':
if(b==1){
count++;
b=0;
t++;
break;
}
else
goto endloop;
default:
goto endloop;
}
}
if(count==nlines){
if(h==t){
res[i]=0;
}
else
res[i]=1;
}
else
endloop:res[i]=1;
}
for(int k=0;k<testcase;k++)
{
int l= res[k];
std::cout<<result[l];
std::cout<<"\n";
}
return 0;
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwojaW5jbHVkZSA8aW9zdHJlYW0+CmludCBtYWluKCkKewppbnQgdGVzdGNhc2UsbmxpbmVzLGk7CnN0ZDo6Y2luPj50ZXN0Y2FzZTsKaW50IHJlc1t0ZXN0Y2FzZV07CmNoYXIgcmVzdWx0WzJdWzhdPXsiVmFsaWQiLCJJbnZhbGlkIn07CmZvcihpPTA7aTx0ZXN0Y2FzZTtpKyspewppbnQgY291bnQ9MCxoPTAsYj0wLHQ9MDsKc3RkOjpjaW4+Pm5saW5lczsKY2hhciBhW25saW5lc107CnN0ZDo6Y2luPj5hOwpmb3IoaW50IGo9MDtqPG5saW5lcztqKyspewpzd2l0Y2goYVtqXSl7CmNhc2UgJ0gnOgppZihiPT0wKXsKY291bnQrKzsKYj0xOwpoKys7CmJyZWFrOwp9CmVsc2V7CmdvdG8gZW5kbG9vcDsKfQpjYXNlICcuJzoKY291bnQrKzsKYnJlYWs7CmNhc2UgJ1QnOgppZihiPT0xKXsKY291bnQrKzsKYj0wOwp0Kys7CmJyZWFrOwp9CmVsc2UKICAgIGdvdG8gZW5kbG9vcDsKZGVmYXVsdDoKZ290byBlbmRsb29wOwp9Cn0KaWYoY291bnQ9PW5saW5lcyl7CmlmKGg9PXQpewpyZXNbaV09MDsKfQplbHNlCnJlc1tpXT0xOwp9CmVsc2UKZW5kbG9vcDpyZXNbaV09MTsKfQpmb3IoaW50IGs9MDtrPHRlc3RjYXNlO2srKykKewppbnQgbD0gcmVzW2tdOwpzdGQ6OmNvdXQ8PHJlc3VsdFtsXTsKc3RkOjpjb3V0PDwiXG4iOwp9CnJldHVybiAwOwp9Cg==