성가신 공구들

잠입 요원 잉코 그니토가 우주선 엔터십 스타프라이즈에 숨어들어 수석 기관사 포지의 수리를 돕게 되었다. 포지는 공구 $N$개를 가져왔고, 수리를 하면서 그 가운데 몇 개를 골라 이름으로 부르며 요청한다. 잉코가 요청받은 공구를 정확히 그대로, 하나도 빠뜨리지 않고 하나도 더하지 않은 채 내밀었을 때만 포지가 받아서 쓰고 다시 돌려준다. 그러면 다음 요청이 이어진다.

문제는 잉코가 공구 이름을 하나도 모른다는 것이다. 눈앞의 공구를 서로 구분하기는 하지만, 어느 공구가 어떤 이름인지는 전혀 모른다. 다만 포지가 이름을 몇 개 부르는지는 셀 수 있어서 요청받은 공구의 개수 $M$은 언제나 안다. 전에 들은 이름이 다시 나오면 같은 이름이라는 것도 알아채므로, 같은 이름은 항상 같은 공구를 가리킨다.

잉코는 눈치가 빨라서 지금까지의 실패와 성공이 알려 주는 정보를 모두 쓴다. 한 번 내밀 때마다 포지는 맞았는지 틀렸는지만 알려 주고, 잉코는 지금까지 받은 답 전부에서 논리적으로 따라 나오는 것을 남김없이 알아낸다. 또 잉코는 자기가 아는 것에 비추어 아직 가능성이 남은 묶음만 내민다.

잉코의 운이 최악이라고 하자. 즉 모든 요청에서 정답인 묶음이 아직 가능한 묶음 가운데 가장 마지막에 시도된다고 하자. 이때 잉코가 작업 전체에서 포지에게 내미는 묶음이 모두 몇 개인지 구하라. 각 요청의 마지막에 포지가 받아 준 묶음도 개수에 넣는다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 공구의 개수 $N$과 포지가 요청하는 묶음의 개수 $K$가 주어진다. 둘째 줄에는 공구 $N$개의 이름이 공백으로 구분되어 주어진다. 이름의 길이는 25 이하이고, 알파벳 소문자 a부터 z까지와 하이픈만 쓴다. 이어지는 $K$개의 줄에는 각각 정수 $M$과 서로 다른 공구 이름 $M$개가 주어지며, 이 $K$개의 줄이 포지의 요청을 순서대로 나타낸다. 한 테스트 케이스 안에서 공구 이름은 모두 다르고, 요청되는 $K$개의 묶음도 서로 모두 다르다. 서로 다른 테스트 케이스의 공구 사이에는 아무 관계가 없다.

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

각 테스트 케이스마다 잉코가 내밀어야 할 수도 있는 묶음의 최대 개수를 한 줄에 하나씩 출력한다. 답이 매우 커질 수 있으므로 $2^{31} - 1 = 2147483647$로 나눈 나머지를 출력한다.