#include<bits/stdc++.h>
using namespace std;
int main(){
long long a;cin>>a;
while(a--){
long long x;cin>>x;
string s;cin>>s;
stack<char>st;
bool no=0;
for(long long i=0;i<s.size();i++){
if(s[i]=='H')st.push('H');
if(st.size()>1)no=1;
if(s[i]=='T' && st.size()>0)st.pop();
}
cout<<((no||st.size()>0)?"Invalid":"Valid")<<endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG1haW4oKXsKCWxvbmcgbG9uZyBhO2Npbj4+YTsKCXdoaWxlKGEtLSl7CgkJbG9uZyBsb25nIHg7Y2luPj54OwoJCXN0cmluZyBzO2Npbj4+czsKCQlzdGFjazxjaGFyPnN0OwoJCWJvb2wgbm89MDsKCQlmb3IobG9uZyBsb25nIGk9MDtpPHMuc2l6ZSgpO2krKyl7CgkJCWlmKHNbaV09PSdIJylzdC5wdXNoKCdIJyk7CgkJCWlmKHN0LnNpemUoKT4xKW5vPTE7CgkJCWlmKHNbaV09PSdUJyAmJiBzdC5zaXplKCk+MClzdC5wb3AoKTsKCQl9CgkJY291dDw8KChub3x8c3Quc2l6ZSgpPjApPyJJbnZhbGlkIjoiVmFsaWQiKTw8ZW5kbDsKCX0KfQo=