#include <iostream>

#include <cstdio>

#include <cstring>

#define ll long long

using namespace std;

int n;

int sta[];

ll dp[][<<];

int calc[][<<],cnt[];

void init()

{

    memset(calc,,sizeof calc);

    memset(cnt,,sizeof cnt);

    for (int i=;i<(<<);i++) //这里把只有一门课 两门。。。N门课全部用一个数组存起来，calc[i][]就代表有i个课程的状态，因为不止一种 所以开了两维。

    {

        int tmp=;

        for (int j=i;j;j>>=)

        {

            if (j&)

                tmp++;

        }

        calc[tmp][cnt[tmp]++]=i;

    }

}

int main()

{

    int t,a;

    scanf("%d",&t);

    init();

    while (t--)

    {

      scanf("%d",&n);

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

      {

          sta[i]=;

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

          {

              scanf("%d",&a);

              if (a==)

              {

                  sta[i]+=<<j;//存入学生感兴趣的课程的状态。

              }

          }

      }

      int p=,all=(<<n)-;

      //memset(dp,0,sizeof dp);

      dp[][]=;

      for (int i=;i<n;i++)//从第0个人循环到第n-1个人

      {

          for (int k=,s=calc[i+][k];k<cnt[i+]&&calc[i+][k]<=all;s=calc[i+][++k])//当前是第i号人 则状态必定是calc[i+1][]的状态，比如第三个人就只分配三个课程即可，一旦可行 就从分配了两个课程的状态那里转移过来。

          {

              dp[p][s]=;

              for (int j=;j<n;j++)//逐个试探第j号课程是否可以

              {

                  //dp[p][k]=0;

                 if (((<<j)&sta[i])==) continue;

                  if ((<<j)&s)

                  {

                      //dp[p][k]+=1;

                       dp[p][s]+=dp[p^][(<<j)^s];//一旦该状态可以，则从上一次的不含新分配的课程的那里转移过来

                  }

                 //else

                  //  dp[p][k]+=dp[p^1][k];

              }

          }

          p^=;

      }

      printf("%lld\n",dp[p^][all]);

    }

    return ;

}