Troublesome Tools

Inco Gnito has sneaked aboard the starship Entership Starprise and has been put to work helping the chief engineer, Forgie, with repairs. Forgie brought $N$ tools with him. While repairing, he keeps asking for some of them by name, and he takes the tools only when Inco hands over exactly the requested set, with no tool missing and no tool extra. He then uses them, gives them back, and the next request follows.

The trouble is that Inco does not know a single tool name. He can tell the tools apart by looking at them, but he has no idea which name belongs to which tool. He can count how many names Forgie says, so he always knows the size $M$ of the requested set. He also recognizes a name he has heard before, so the same name always means the same tool.

Inco is a quick study and uses everything his earlier failures and successes tell him. Each time he hands over a set, Forgie says only whether it is right or wrong, and Inco works out everything that follows logically from all the answers so far. Inco hands over only a set that is still possible given what he knows.

Assume Inco is as unlucky as he can be, so that in every request the correct set is the last of the still possible sets he tries. Count how many sets Inco hands to Forgie over the whole assignment. The set that Forgie accepts at the end of each request counts too.

The first line has one integer $T$, the number of test cases. Each test case starts with a line holding two integers $N$, the number of tools, and $K$, the number of sets Forgie asks for. The next line has the $N$ tool names separated by spaces. A name is at most 25 characters long and uses only the lowercase letters a to z and the hyphen. Each of the next $K$ lines holds an integer $M$ followed by the names of $M$ different tools, and these $K$ lines give Forgie's requests in order. Tool names are distinct within a test case, the $K$ requested sets are pairwise different, and tools of different test cases have nothing to do with each other.

• $0 < T \le 100$
• $0 < N \le 1000$
• $0 < K \le 100$
• $0 < M \le N$

For each test case, print on its own line the largest number of sets Inco may have to hand over. The answer can be very large, so print it modulo $2^{31} - 1 = 2147483647$.