#include <cstdio>
#include <memory.h>
#include <map>
#include <algorithm>
using namespace std;
const int MOD = 1000000009;
bool check[21][(1<< 20)];
map<int,int> DT[21];
int dbit[21];
int n,m;
int memo(int submit,int accept,int discard)
{
        if(accept == 0)return 1;
        if(check[submit][accept])return DT[submit][accept];
        int d = 0;
        check[submit][accept] = true;
        for(int i = 0; i < m; i++)
        {
                if(accept & (1 << i))
                {
                        int t = __builtin_popcount(discard | dbit[i]) - (n - submit);
                        if(submit / 2 >= t)
                        {
                                d += memo(submit - t,accept & ~(1 << i), (discard | dbit[i])) % MOD; 
                        }

                }
        }
        return DT[submit][accept] = d;
}
int main()
{
        int T;
        scanf("%d",&T);
        while(T--)
        {
                scanf("%d%d",&n,&m);
                memset(check,false,sizeof(check));
                for(int i = 0;i <= n; i++)DT[i].clear();
                for(int i = 0; i < m;i++)
                {
                        int a,t;
                        scanf("%d",&t);
                        dbit[i] = 0;
                        for(int j = 0;j < t; j++)
                        {
                                scanf("%d",&a);
                                dbit[i] |= (1 << a);
                        }
                }
                printf("%d\n",memo(n,(1 << m) - 1,0));

        }

}