# your code goes here
def validate(string):
    head = False
    tail = False
    for c in string:
        if c == 'H':
            if (not head and not tail):
                head = True
            else:
                return ("Invalid")
        if c == "T":
            if (head and not tail):
                head = False
            else:
                return ("Invalid")
    if not head:
        return ("Valid")
    else:
        return ("Invalid")
 
tc = int(input())
for etc in range(tc):
    length = input()
    string = input()
    print (validate(string))
 

IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmRlZiB2YWxpZGF0ZShzdHJpbmcpOgogICAgaGVhZCA9IEZhbHNlCiAgICB0YWlsID0gRmFsc2UKICAgIGZvciBjIGluIHN0cmluZzoKICAgICAgICBpZiBjID09ICdIJzoKICAgICAgICAgICAgaWYgKG5vdCBoZWFkIGFuZCBub3QgdGFpbCk6CiAgICAgICAgICAgICAgICBoZWFkID0gVHJ1ZQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgcmV0dXJuICgiSW52YWxpZCIpCiAgICAgICAgaWYgYyA9PSAiVCI6CiAgICAgICAgICAgIGlmIChoZWFkIGFuZCBub3QgdGFpbCk6CiAgICAgICAgICAgICAgICBoZWFkID0gRmFsc2UKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHJldHVybiAoIkludmFsaWQiKQogICAgaWYgbm90IGhlYWQ6CiAgICAgICAgcmV0dXJuICgiVmFsaWQiKQogICAgZWxzZToKICAgICAgICByZXR1cm4gKCJJbnZhbGlkIikKIAp0YyA9IGludChpbnB1dCgpKQpmb3IgZXRjIGluIHJhbmdlKHRjKToKICAgIGxlbmd0aCA9IGlucHV0KCkKICAgIHN0cmluZyA9IGlucHV0KCkKICAgIHByaW50ICh2YWxpZGF0ZShzdHJpbmcpKQog

NgoxOAouLkguLlQuLi5IVEguLi4uVC4KMwouLi4KMTAKSC4uSC4uVC4uVAoyCkhUCjExCi5ULi4uSC4uSC5UCjcKSC4uVC4uSA==

6
18
..H..T...HTH....T.
3
...
10
H..H..T..T
2
HT
11
.T...H..H.T
7
H..T..H