eow

#include<iostream>
#include<cstdio>
#include<cstring>
#define gc getchar_unlocked
#define pc putchar_unlocked

using namespace std;

#define MAX_NUM 10000000


bool status[10000010];                //if status[i]=1 that means i is a prime num and if i is not prime status[i]=0
int pos[10000010];                    //if a num i is prime then pos[i] will store the serial num. of this prime num
                                     //like status[2]=1 and pos[2]=1
                                     //status[5]=1 and pos[5]=3

void gen_sieve_primes(void)     //function to implement sieve of eratosthenes
{
    int cnt=0;
    int c;

    status[0]=0;
    status[1]=0;               // Because 0 and 1 are not prime

    for (int p=2; p<MAX_NUM; p++)     // for all elements in array
    {
        if(status[p] == 1)     // it is not multiple of any other prime
        {
            cnt++;
            pos[p]=cnt;

            // mark all multiples of prime selected above as non primes
            c=2;
            int mul = p * c;

            for(; mul < MAX_NUM;)
            {
                status[mul] = 0;
                c++;
                mul = p*c;
            }

        }

    }
}



void scanint(int &x)        //function to input integer using getchar function
{
  char c = gc();

  while(c<'0' || c>'9')
   c = gc();

  x=0;

  while(c>='0' && c<='9')
  {
   x = 10 * x + c - 48;
   c = gc();
  }

}



//recursive function to implement grid hacking mechanism
//first it cracks x_s[i][j] then recursively crack the connected
//servers which are x_s[i][j-1], x_s[i][j+1], x_s[i-1][j] and x_s[i+1][j]

void crackconnected(int x_s[][352],bool x_f[][352],int i,int j,int n,int o_e)        // n is the no. of servers in a row and o_e=0 for even server
{                                                                                    // and o_e=1 for odd server
    if((i>=1)&&(j>=1)&&(i<=n)&&(j<=n))
    {                                                                 // constraints- bounds checking
        if((x_f[i][j]==0)&&(x_s[i][j]%2==o_e))                        // checking if server is already cracked
        {                                                             // and check for odd/even server
            int r=x_s[i][j];

            if(status[r]==0)                                          // checking if the number is prime
           {
               x_f[i][j]=1;
               crackconnected(x_s,x_f,i,j+1,n,o_e);
               crackconnected(x_s,x_f,i+1,j,n,o_e);
               crackconnected(x_s,x_f,i-1,j,n,o_e);
               crackconnected(x_s,x_f,i,j-1,n,o_e);
           }
        }
    }
}



void process(int x_s[][352],bool x_f[][352],int n)                    // function to crack all the servers
{
    int i,j,b;
    long long int o=0;                                 // o will store the no. of unsuccessful tries

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {

          if(x_f[i][j]==0)
          {

           b=x_s[i][j];

           if(status[b]==1)                    //if x_s[i][j] is a prime num
           {
               //prime server
               o=o+(pos[b])-1;
               x_f[i][j]==1;
           }

           else if(x_s[i][j]%2==0)                   //if x_s[i][j] is an even server
           {
               //even server
               o=o + ((x_s[i][j])/2);
               crackconnected(x_s,x_f,i,j,n,0);
           }

           else                                      //if x_s[i][j] is an odd server
           {
               //odd server
               o=o + (((x_s[i][j])+3)/2);
               crackconnected(x_s,x_f,i,j,n,1);
           }

           //if condition (if(x_f[i][j]==0)) ends here
          }

        }
    }

 printf("%lld",o);                                    //this is the result of the existing test case
}




int main()
{
    int t,i,j,k,n;

    memset(status,1,MAX_NUM);
    gen_sieve_primes();

    int server_s[352][352];             //this stores the password for the server
    bool server_f[352][352];            //this stores the status of the server. Initially all zero indicating uncracked and f=0 indicates cracked server

    scanf("%d",&t);

    for(i=1;i<=t;i++)
    {
        scanf("%d",&n);

        for(j=1;j<=n;j++)
        {
            for(k=1;k<=n;k++)
            {
                scanint(server_s[j][k]);
                server_f[j][k]=0;
            }
        }

        process(server_s,server_f,n);

        pc('\n');

    }

 return 0;
}