#include<bits/stdc++.h>
using namespace std;

int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        int n,i,h=0,t=0,temp=0,k=0;
        scanf("%d",&n);
        getchar();
        char a[n];
        gets(a);
        for(i=0; i<n; i++)
        {
            if(a[i]=='H')
            {
                h++;
                for(int j=i+1; j<n; j++)
                {
                    if(a[j]=='H'||a[j]=='T')
                    {
                        temp=j;
                        break;
                    }
                }
                if(a[temp]=='H')
                {
                    k=1;
                    goto u;
                }
                else
                {
                    t++;
                    i=temp;
                }
            }
            else if(a[i]=='T')
            {
                t++;
                for(int j=i+1; j<n; j++)
                {
                    if(a[j]=='H'||a[j]=='T')
                    {
                        temp=j;
                        break;
                    }
                    if(a[temp]=='T')
                    {
                        k=1;
                        goto u;
                    }
                    else
                    {
                        h++;
                        i=temp;
                    }
                }
            }
        }
u:
        cout<<h<<" "<<t<<" "<<endl;
        if(t!=h|| k==1)
        {
            cout<<"Invalid"<<endl;
        }
        else
        {
            cout<<"Valid"<<endl;
        }
    }
}