#include<bits/stdc++.h>
#define all(v) ((v).begin()),((v).end())
#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;
rep(i,x){
if(s[i]=='H')st.push('H');
if(st.size()>1){no=1;break;}
if(s[i]=='T' && st.size()>0)st.pop();
}
cout<<((no||st.size()>0)?"Invalid":"Valid")<<endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBhbGwodikgKCh2KS5iZWdpbigpKSwoKHYpLmVuZCgpKQojZGVmaW5lIHJlcChpLG4pIGZvcihpbnQoaSk9MDsoaSk8KGludCkobik7KGkpKyspCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgbWFpbigpewoJaW50IGE7Y2luPj5hOwoJd2hpbGUoYS0tKXsKCQlpbnQgeDtjaW4+Png7CgkJc3RyaW5nIHM7Y2luPj5zOwoJCXN0YWNrPGNoYXI+c3Q7CgkJYm9vbCBubz0wOwoJCXJlcChpLHgpewoJCQlpZihzW2ldPT0nSCcpc3QucHVzaCgnSCcpOwoJCQlpZihzdC5zaXplKCk+MSl7bm89MTticmVhazt9CgkJCWlmKHNbaV09PSdUJyAmJiBzdC5zaXplKCk+MClzdC5wb3AoKTsKCQl9CgkJY291dDw8KChub3x8c3Quc2l6ZSgpPjApPyJJbnZhbGlkIjoiVmFsaWQiKTw8ZW5kbDsKCX0KfQo=