Redistributing Gifts

Farmer John has $N$ gifts labeled $1\ldots N$ for his $N$ cows, also labeled $1\ldots N$ ($1\le N\le 18$). Each cow has a wishlist, which is a permutation of all $N$ gifts. A cow prefers gifts that appear earlier in her list over gifts that appear later.

FJ was lazy and just assigned gift $i$ to cow $i$ for all $i$. Now the cows have gathered and decided to reassign the gifts. After reassignment, every cow must end up with either the same gift she originally had or a gift she prefers over it.

There is one more constraint. A gift may only be reassigned to a cow if the gift was originally assigned to a cow of the same breed. Each cow is either a Holstein or a Guernsey. You are given $Q$ breed strings of length $N$ ($1\le Q\le \min(10^5,2^N)$). For each string, count the reassignments that are consistent with it.

The first line contains $N$. The next $N$ lines each contain the preference list of one cow, a permutation of $1\dots N$. The next line contains $Q$. The final $Q$ lines each contain a breed string of length $N$ made only of the characters G and H. No breed string occurs more than once.

For each breed string, print the number of reassignments consistent with it on a new line.

In the sample, the first breed string allows two reassignments. The first is the original assignment: cow 1 gets gift 1, cow 2 gets gift 2, cow 3 gets gift 3, and cow 4 gets gift 4. The second has cow 1 with gift 1, cow 2 with gift 3, cow 3 with gift 2, and cow 4 with gift 4. For the second breed string, the only consistent reassignment is the original assignment.