UEl Granjero Juan tiene ~N~ regalos rotulados ~1...N~ para sus ~N~ vacas, también rotuladas ~1...N~. Cada vaca tiene una lista de deseos, la cual es una permutación de todos los ~N~ regales de tal manera que la vcaca prefiere los regalos que aparece nantes en la lista más que los regalos que aparecen después en la lista.

GJ estaba con pereza y simplemene asignó el regalo ~i~ a la vaca ~i~ para todo ~i~. Ahora, las vacas se han reunido entre allas y decidieron reasignar los regales de manera que después de la reasignación, cada vaca termine con el mismo regalo que tenía originalmente, o un regalo que ella prefiera más que el que tenía asignado originalmente.

Hay también una restricción original: un regalo solamente puede ser reasignado a una vaaca que si estaba asignado originalmente a una vaca del mismo tipo (cada vaca es o una Holstein o una Guernsey). Dadas ~Q~ cadenas de razas de longitud ~N~, para cada una cuente el número de reasignaciones que con consiente con ella.

Entrada

• La primera línea contiene a ~N~.
• Cada una de las ~N~ líneas siguientes contiene la lista de preferencia de una vaca. Se garantiza que cada línea es una permutación de ~1...N~.
• La siguiente línea contiene a ~Q~.
• Cada una de las ~Q~ líneas restantes contiene una cadena de raazas, cada una con ~N~ caracteres de longitud y consistiendo solamente de los caracteres G y H. Ninguna cadena de razas aparece más de una vez.

Salida

Para cada cadena de razas, imprima el número de reasignaciones que con son consitente con ella en una nueva línea.

Restricciones

• ~1 \leq N \leq 18~
• ~1 \leq Q \leq min(10^5,2^N)~

Ejemplo de Entrada

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG

Ejemplo de Salida

2
1
1
2
2

En este ejemplo, para la primera cadena de razas, hay dos reasignaciones posibles:

• La asignación original: la vaca 1 recibe el regalo 1, la vaca 2 recibe el regalo 2, la vaca 3 recibe el regalo 3, y la vaca 4 recibe el regalo 4.
• La vaca 1 recibe el regalo 1, la vaca 2 recibe el regalo 3, la vaca 3 recibe el regalo 2, y la vaca 4 recibe el regalo 4.

Para la segunda cadena de razas, la única reasignacion consisente con ella es la asignación original.

USACO 2022 February Contest, Gold Problem 1. Redistributing Gifts.