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 Output for Sample Input

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

把所有可能轉換出來之後，全部記錄，接著再開始對查詢輸出結果。

#include <stdio.h>
#include <queue>
using namespace std;
int main() {
    int t, cases = 0, n, m;
    char bin[20];
    scanf("%d", &t);
    while(t--) {
        printf("Case %d:\n", ++cases);
        scanf("%d %d", &n, &m);
        int mark[40] = {}, x, y;
        int i, j;
        for(i = 0; i < m; i++) {
            scanf("%d", &x);
            while(x--) {
                scanf("%d", &y);
                mark[i] |= 1<<y;
            }
        }
        int ans[32768] = {};
        ans[0] = 1;
        queue<int> Q;
        Q.push(0);
        while(!Q.empty()) {
            x = Q.front();
            Q.pop();
            for(i = 0; i < m; i++) {
                if(!ans[x^mark[i]]) {
                    ans[x^mark[i]] = ans[x]+1;
                    Q.push(x^mark[i]);
                }
            }
        }
        scanf("%d", &m);
        while(m--) {
            scanf("%s", bin);
            for(i = 0, x = 0; bin[i]; i++)
                x |= (1&(bin[i]-'0'))<<(n-i-1);
            if(ans[x] == 0)
                puts("-1");
            else
                printf("%d\n", ans[x]-1);
        }
        puts("");
    }
    return 0;
}