선물 재분배

농부 존은 번호가 $1\ldots N$인 선물 $N$개를 번호가 $1\ldots N$인 소 $N$마리에게 나눠 준다 ($1\le N\le 18$). 각 소에게는 모든 선물을 나열한 순열인 선호 목록이 있다. 소는 목록에서 앞에 있는 선물을 뒤에 있는 선물보다 선호한다.

존은 게을러서 모든 $i$에 대해 선물 $i$를 소 $i$에게 그냥 주었다. 이제 소들이 모여 선물을 다시 나누기로 했다. 재분배 후 모든 소는 원래 받았던 선물을 그대로 받거나, 원래 선물보다 더 선호하는 선물을 받아야 한다.

추가 조건도 있다. 선물은 원래 같은 품종의 소에게 주어졌던 경우에만 그 소에게 재분배될 수 있다. 각 소는 홀스타인 또는 건지 중 하나의 품종이다. 길이가 $N$인 품종 문자열이 $Q$개 주어진다 ($1\le Q\le \min(10^5,2^N)$). 각 문자열마다 그 문자열과 맞는 재분배의 수를 구하라.

첫 줄에 $N$이 주어진다. 이어서 $N$개의 줄에 각 소의 선호 목록이 주어지며, 각 줄은 $1\dots N$의 순열이다. 다음 줄에는 $Q$가 주어진다. 마지막 $Q$개의 줄에는 G와 H로만 이루어진 길이 $N$의 품종 문자열이 하나씩 주어진다. 같은 품종 문자열이 두 번 나오지 않는다.

각 품종 문자열에 대해, 그 문자열과 맞는 재분배의 수를 한 줄에 하나씩 출력한다.

이 예제에서 첫 번째 품종 문자열에 대해 가능한 재분배는 두 가지이다. 첫 번째는 원래 배분이다. 소 1은 선물 1, 소 2는 선물 2, 소 3은 선물 3, 소 4는 선물 4를 받는다. 두 번째에서는 소 1이 선물 1, 소 2가 선물 3, 소 3이 선물 2, 소 4가 선물 4를 받는다. 두 번째 품종 문자열과 맞는 재분배는 원래 배분뿐이다.