A

#include<bits/stdc++.h>
using namespace std;
int check(int arr[],int m);
int main()
{
    int n,l,x,m=0,arr[10000],arr2[10000],nu=0;;
    char c;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&l);
        nu=0;
        m=0;
       /* if(i!=0)
        {
            for (int f=0; f< strlen(arr); f++)
            {
                arr[f] = '\0';
            }
        }
        */
        for(int j=0; j<l; j++)
        {
            scanf(" %c",&c);
            if(c=='.')
            {
                arr[nu]=0;
                nu++;
            }
            if(c=='H' || c=='T')
            {
                if(c=='H')
                {
                    arr[m]=1;
                    m++;
                }
                else
                {
                    arr[m]=2;
                    m++;
                }

            }
        }
        //x=sizeof(arr)/sizeof(int);
        //cout<<"size=="<<m<<endl;

        if(nu==l || m==1 && arr[0]==1)
        {
            printf("Invalid\n");
        }
        else if(arr[0]==2 || m%2!=0)
        {
            printf("Invalid\n");
        }
        else
        {
            int p=check(arr,m);
            if(p==0)
            {
                printf("Valid\n");

                //cout<<"yes1";
            }
            else if(p==-1)
            {
                printf("Invalid\n");
                //cout<<"yes2";
            }
        }

    }
    return 0;
}
int check(int arr[],int m)
{
    for(int i=0; i<m; i++)
    {
       // printf("%d%d\n",arr[i],arr[i+1]);

        //printf("%d%d\n",arr[i],arr[i+1]);
        if(i%2==0 &&arr[i]==1 || i%2!=0 && arr[i]==2)
        {
            ;
        }
        else
            return -1;
    }
    return 0;
}