Los gatos de nuestro amigo Botas desaparecieron, Botas se encuentra muy triste y para llenar ese vacio que sus gatos dejaron, Botas decidio aprender electronica y comenzo a crear robots que lo acompañen en su soledad, lo interesante de estos robots ademas de ser autonomos, era la capacidad que teni­an para aumentar la longitud de sus brazos a su antojo. Despues de unos dias Botas se dio cuenta que habi­a creado demasiados robots. Al ver esto, decidio que estos robots compitan. Botas catalogo a los robots en dos tipos (tipo A y tipo B) . La idea de este concurso es que los robots estan emparejados (es decir dos robots se toman de los brazos). Las reglas de emparejamiento son las siguientes:

• Un emparejamiento debe ser de dos robots del mismo tipo
• Dentro de un emparejamiento valido pueden existir varios emparejamientos que ademas deben ser validos (esto es posible por la capacidad que tienen los robots de aumentar la longitud de sus brazos).
• Dos emparejamientos no pueden entrelazarse
• Todo robot debe tener una pareja

Como Botas sigue en segundo semestre, aun no conoce algunas trucos de programacion, es por eso que debes ayudar a Botas creando un programa que dado el estado final de los robots, ayude a Botas a ver si dicho estado es valido o no. Algunos ejemplos de estados validos e invalidos son:

La primera linea contiene un numero $T$ ($1 \leq T \leq 50$) que es la cantidad de casos. Cada caso comienza con un número $N$ ($1 \leq N \leq 100$) que es la cantidad de robots, luego viene una cadena S de tamaño $N$ que representa el estado final de los robots, cada caracter representa a un robot, los robots de tipo A estan representados por los caracteres "{" y "}" los robots del tipo B estan representados por "["€, "]"€.

Por cada caso, se debe imprimir “V” si el estado es v ́lido y “NV” si no lo es.