Switch Bulbs

Input: Standard Input

Output: Standard Output

You are given n bulbs and m switches. Each of the switches toggles a list of bulbs. Initially all the bulbs are turned off. Now for a set of desired states of the bulbs calculate the minimum number of switch presses required to reach that state.

Input

Input contains multiple test cases. First line contains an integer T the number of test cases. Each test case starts with a line containing 2 integers n (1≤n≤15) and m (1≤m≤40). Next m line contains the description of m switches. Each of these lines starts with an integer k denoting the number of bulbs that toggles their states after pressing this switch. The rest of the line contains k distinct integers denoting the indices of the bulbs. The bulbs are numbered from 0 to n-1. The next line contains an integer q(1≤q≤5000) that denotes the number of queries. Each of the following q line contains a binary string of length n denoting the desired states of the n bulbs: 1 means the bulb must be on and 0 means the bulb must be off. The rightmost character is the state of bulb 0 and the leftmost character is the state of bulb n-1.

Output

For each test case output contains q+2 lines. First line contains “Case x:” where x is the number of test cases. Each of the next q lines contains one integer denoting the minimum number of switch presses required to reach the bulb states in the i’th query. If the state cannot be reachable by a series of switch presses output -1. The last line will be a blank line.

Sample Input Output for Sample Input

3 3

3 0 1 2

2 1 2

1 2

101

010

111

4 5

1 0

1 1

2 2 3

3 0 1 3

2 2 3

1111

1010

0101

Case 1:

Case 2:

Problem setter: Abdullah al Mahmud, Special thanks: S. Hafiz, Md. Arifuzzaman, S. Manzoor