#include<bits/stdc++.h>
using namespace std;
bool verifyH(char x){return (x==‘H’);}
bool verifyT(char x){return (x==‘T’);}
bool verifydot(char x){return (x==’.’);}
int main()
{
int tc;
cin>>tc;
while(tc–)
{
int n;
cin>>n;
char s[n];
cin>>s;
int d = count_if(s,s+n,verifydot);
if(d==n){cout<<“Invalid”<<endl;break;}
vector a;
for(int i=0;i<n;i++)
{
if(s[i]==‘H’ || s[i]==‘T’)
{
a.push_back(s[i]);
}
}
int temp = 0;
int h = count_if(a.begin(),a.end(),verifyH);
int t = count_if(a.begin(),a.end(),verifyT);
if(h!=t)
{
cout<<“Invalid”<<endl;
}
else if(h==t)
{
for(int i=0;i<a.size();i++)
{
if(a[i]==a[i+1])
{
temp = -1;
}
}
if(temp==-1)cout<<“Invalid”<<endl;
else if(temp==0)cout<<“Valid”<<endl;
}
}
return 0;
}