#include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 int n, m;

 int num;

 char s[maxn];

 struct Bitset//用unsigned数组实现bitset，为了使用__builtin_ctz()

 {

     unsigned v[];//8个unsigned表示8*32=256位

     void reset()//清零

     {

         for(int i=;i<;++i) v[i]=;

     }

     void set(int x)//把某一位设为1

     {

         v[x>>]|=1u<<(x&);

     }

     void flip(int x)//翻转某一位

     {

         v[x>>]^=1u<<(x&);

     }

     bool test(int x)//返回某一位是否为1

     {

         return v[x>>]>>(x&)&;

     }

 }vis, G[maxn], rG[maxn];

 vector<int> S;

 void dfs1(int u)

 {

     vis.flip(u);

     for(int i=;i<;i++)

     {

         while(true)

         {

             unsigned tmp=vis.v[i]&G[u].v[i];  //tmp就计算出了可以访问的点

             if(!tmp)  break;

             dfs1(i<<|__builtin_ctz(tmp));  //计算出tmp末尾有多少0，有多少0就代表了它是第几位，这儿的话一个点一个点的来

         }

     }

     S.push_back(u);

 }

 void dfs2(int u)

 {

     vis.flip(u);

     ++num;

     for(int i=;i<;i++)

     {

         while(true)

         {

             unsigned tmp=vis.v[i]&rG[u].v[i];

             if(!tmp)  break;

             dfs2(i<<|__builtin_ctz(tmp));

         }

     }

 }

 void Kosaraju()

 {

     S.clear();

     int ans=;

     for(int i=;i<n;i++)  vis.set(i);

     for(int i=;i<n;i++)  if(vis.test(i))  dfs1(i);

     for(int i=;i<n;i++)  vis.set(i);

     for(int i=n-;i>=;i--)

     {

         if(vis.test(S[i]))

         {

             num=;

             dfs2(S[i]);

             ans+=num*(num-)/;

         }

     }

     printf("%d\n",ans);

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         for(int i=;i<n;i++) G[i].reset(),rG[i].reset();

         for(int i=;i<n;i++)

         {

             scanf("%s",s);

             for(int j=;j<n;j++)  if(s[j]=='')

             {

                 G[i].flip(j);

                 rG[j].flip(i);

             }

         }

         while(m--)

         {

             int t; scanf("%d",&t);

             while(t--)

             {

                 int u,v;

                 scanf("%d%d",&u,&v);

                 G[u-].flip(v-);

                 rG[v-].flip(u-);

             }

             Kosaraju();

         }

     }

     return ;

 }