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

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KICAgICNkZWZpbmUgcmVwKGksbikgZm9yKGludChpKT0wOyhpKTwoaW50KShuKTsoaSkrKykKICAgIHR5cGVkZWYgbG9uZyBsb25nIGxsOwogICAgdXNpbmcgbmFtZXNwYWNlIHN0ZDsKICAgIGludCBtYWluKCl7CiAgICAJaW50IGE7Y2luPj5hOwogICAgCXdoaWxlKGEtLSl7CiAgICAJCWludCB4O2Npbj4+eDsKICAgIAkJc3RyaW5nIHM7Y2luPj5zOwogICAgCQlzdGFjazxjaGFyPnN0OwogICAgCQlib29sIG5vPTAsc3RhcnQ9MDsKICAgIAkJcmVwKGksKGludClzLnNpemUoKSl7CiAgICAJCQlpZihzW2ldPT0nSCcpc3QucHVzaCgnSCcpLHN0YXJ0PTE7CiAgICAJCQlpZihzdC5zaXplKCk+MSlubz0xOwogICAgCQkJaWYoc1tpXT09J1QnICYmIHN0LnNpemUoKT4wKXN0LnBvcCgpOwogICAgCQl9CiAgICAJCWNvdXQ8PCgoIXN0YXJ0fHxub3x8c3Quc2l6ZSgpPjApPyJJbnZhbGlkIjoiVmFsaWQiKTw8ZW5kbDsKICAgIAl9CiAgICB9IAoK