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 ith 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 2 33 3012 212 12 3 101 010 111 45 10 11 223 3013 223 3 1111 1010 0101
2/2 Sample Output Case 1: 3 2 1 Case 2: 3 2 3