#include<bits/stdc++.h>
using namespace std;
int main( ) {
long long a; cin >> a;
while ( a-- ) {
ll 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+YTsKCXdoaWxlKGEtLSl7CgkJbGwgeDtjaW4+Png7CgkJc3RyaW5nIHM7Y2luPj5zOwoJCXN0YWNrPGNoYXI+c3Q7CgkJYm9vbCBubz0wOwoJCWZvcihsb25nIGxvbmcgaT0wO2k8cy5zaXplKCk7aSsrKXsKCQkJaWYoc1tpXT09J0gnKXN0LnB1c2goJ0gnKTsKCQkJaWYoc3Quc2l6ZSgpPjEpbm89MTsKCQkJaWYoc1tpXT09J1QnICYmIHN0LnNpemUoKT4wKXN0LnBvcCgpOwoJCX0KCQljb3V0PDwoKG5vfHxzdC5zaXplKCk+MCk/IkludmFsaWQiOiJWYWxpZCIpPDxlbmRsOwoJfQp9Cg==