Los gatos de nuestro amigo Botas desaparecieron, Botas se encuentra muy triste y para llenar ese vacío que sus gatos dejaron, Botas decidió aprender electrónica y comenzó a crear robots que lo acompañen en su soledad, lo interesante de estos robots además de ser autónomos, era la capacidad que tenían para aumentar la longitud de sus brazos a su antojo. Después de unos días Botas se dio cuenta que había creado demasiados robots. Al ver esto, decidió que estos robots compitan. Botas catalogó a los robots en dos tipos (tipo A y tipo B) . La idea de este concurso es que los robots estén 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 válido pueden existir varios emparejamientos que además deben ser válidos (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

Después que los robots buscan la mejor forma de emparejarse, estos llegan a un estado final y Botas debe verificar si este estado cumple con las reglas de emparejamiento. Como Botas sigue en segundo semestre, aún no conoce algunas trucos de programación, 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 válido o no. Algunos ejemplos de estados válidos e inválidos son:

La primera linea contiene un número T (1¡= T ¡= 50) que es la cantidad de casos. Cada caso comienza con un número N (1¡= N ¡= 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 están representados por los caracteres “{”, “}” y los robots del tipo B están representados por “[”, “]”.

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

Los casos secretos fueron GENERADOS en 2026 y no pertenecen al banco histórico. No se han verificado soluciones en Patito.