#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define LIMIT 10000000 /*size of integers array*/
#define PRIMES 700000 /*size of primes array*/
#define N 351
int numbers[LIMIT];// numbers[i] is -1 if it is not prime otherwise numbers[i] = i+2
int primes[PRIMES];// list of prime numbers 2,3,5,7...
int a[N][N]; // passwords of server[i][j]
bool b[N][N]; // is true if b[i][j] has been cracked by grid hacking mechanism
bool even[N][N];// even[i][j] = true if password of server is nonprime even, otherwise false
bool odd[N][N];// odd[i][j] = true if password of server is nonprime odd, otherwise false
bool memo1[N][N];// return true when memo1[i][j] has been visited once in grid hacking mechanism of even numbers function
bool memo2[N][N];// return true when memo2[i][j] has been visited once in grid hacking mechanism of odd numbers function
int bSearch(int x, int low, int high){
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (x < primes[mid])
high = mid - 1;
else if (x > primes[mid])
low = mid + 1;
else
return mid;
}
return -1;
}
void gridhackeven(int i, int j, int n) {
if (memo1[i][j] == true)
return;
memo1[i][j] = true;
b[i][j] = true;
if (j+1 <= n-1 && even[i][j+1] == true) {
b[i][j+1] = true;
gridhackeven(i,j+1,n);
}
if (j-1 >= 0 && even[i][j-1] == true) {
b[i][j-1] = true;
gridhackeven(i,j-1,n);
}
if (i-1 >= 0 && even[i-1][j] == true) {
b[i-1][j] = true;
gridhackeven(i-1,j,n);
}
if (i+1 <= n-1 && even[i+1][j] == true) {
b[i+1][j] = true;
gridhackeven(i+1,j,n);
}
return;
}
void gridhackodd(int i, int j, int n) {
if (memo2[i][j] == true)
return;
memo2[i][j] = true;
b[i][j] = true;
if (j+1 <= n-1 && odd[i][j+1] == true) {
b[i][j+1] = true;
gridhackodd(i,j+1,n);
}
if (j-1 >= 0 && odd[i][j-1] == true) {
b[i][j-1] = true;
gridhackodd(i,j-1,n);
}
if (i-1 >= 0 && odd[i-1][j] == true) {
b[i-1][j] = true;
gridhackodd(i-1,j,n);
}
if (i+1 <= n-1 && odd[i+1][j] == true) {
b[i+1][j] = true;
gridhackodd(i+1,j,n);
}
return;
}
inline void scan(int *a) {
register char c=0;
while (c < 33)
c = getchar_unlocked();
*a = 0;
while (c > 33) {
*a = *a * 10 + c - '0';
c = getchar_unlocked();
}
}
int main(){
int i,j;
/*fill the array with natural numbers*/
for (i=0;i<LIMIT;i++){
numbers[i]=i+2;
}
/*sieve the non-primes*/
for (i=0;i<LIMIT;i++){
if (numbers[i]!=-1){
for (j=2*numbers[i]-2;j<LIMIT;j+=numbers[i])
numbers[j]=-1;
}
}
j = 0;
for (i=0;i<LIMIT&&j<PRIMES;i++)
if (numbers[i]!=-1)
primes[j++] = numbers[i];
int limit = j;
int t, n;
long long count;
scan(&t);
while (t--) {
scan(&n);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scan(&a[i][j]);
b[i][j] = false;
memo1[i][j] = false;
memo2[i][j] = false;
even[i][j] = false;
odd[i][j] = false;
if (numbers[a[i][j]-2] == -1) {
if (a[i][j] % 2 == 0) {
even[i][j] = true;
odd[i][j] = false;
}
else {
odd[i][j] = true;
even[i][j] = false;
}
}
}
}
count = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (b[i][j] != true) {
if (numbers[a[i][j]-2] != -1) {
b[i][j] = true;
count += bSearch(a[i][j],0,limit-1);
}
else if (even[i][j] == true) {
count += (a[i][j]>>1);
gridhackeven(i, j, n);
}
else if(odd[i][j] == true) {
count += ((a[i][j]+1)>>1) +1;
gridhackodd(i, j, n);
}
}
}
}
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGJvb2wuaD4KCiNkZWZpbmUgTElNSVQgMTAwMDAwMDAgLypzaXplIG9mIGludGVnZXJzIGFycmF5Ki8KI2RlZmluZSBQUklNRVMgNzAwMDAwIC8qc2l6ZSBvZiBwcmltZXMgYXJyYXkqLwojZGVmaW5lICAgIE4JMzUxCmludCBudW1iZXJzW0xJTUlUXTsvLyBudW1iZXJzW2ldIGlzIC0xIGlmIGl0IGlzIG5vdCBwcmltZSBvdGhlcndpc2UgbnVtYmVyc1tpXSA9IGkrMgppbnQgcHJpbWVzW1BSSU1FU107Ly8gbGlzdCBvZiBwcmltZSBudW1iZXJzIDIsMyw1LDcuLi4KaW50IGFbTl1bTl07IC8vIHBhc3N3b3JkcyBvZiBzZXJ2ZXJbaV1bal0KYm9vbCBiW05dW05dOyAvLyBpcyB0cnVlIGlmIGJbaV1bal0gaGFzIGJlZW4gY3JhY2tlZCBieSBncmlkIGhhY2tpbmcgbWVjaGFuaXNtCmJvb2wgZXZlbltOXVtOXTsvLyBldmVuW2ldW2pdID0gdHJ1ZSBpZiBwYXNzd29yZCBvZiBzZXJ2ZXIgaXMgbm9ucHJpbWUgZXZlbiwgb3RoZXJ3aXNlIGZhbHNlCmJvb2wgb2RkW05dW05dOy8vIG9kZFtpXVtqXSA9IHRydWUgaWYgcGFzc3dvcmQgb2Ygc2VydmVyIGlzIG5vbnByaW1lIG9kZCwgb3RoZXJ3aXNlIGZhbHNlCmJvb2wgbWVtbzFbTl1bTl07Ly8gcmV0dXJuIHRydWUgd2hlbiBtZW1vMVtpXVtqXSBoYXMgYmVlbiB2aXNpdGVkIG9uY2UgaW4gZ3JpZCBoYWNraW5nIG1lY2hhbmlzbSBvZiBldmVuIG51bWJlcnMgZnVuY3Rpb24KYm9vbCBtZW1vMltOXVtOXTsvLyByZXR1cm4gdHJ1ZSB3aGVuIG1lbW8yW2ldW2pdIGhhcyBiZWVuIHZpc2l0ZWQgb25jZSBpbiBncmlkIGhhY2tpbmcgbWVjaGFuaXNtIG9mIG9kZCBudW1iZXJzIGZ1bmN0aW9uCgppbnQgYlNlYXJjaChpbnQgeCwgaW50IGxvdywgaW50IGhpZ2gpewogICAgaW50IG1pZDsKICAgIHdoaWxlIChsb3cgPD0gaGlnaCkgewogICAgCW1pZCA9IChsb3cgKyBoaWdoKSAvIDI7CiAgICAJaWYgKHggPCBwcmltZXNbbWlkXSkKICAgIAkJaGlnaCA9IG1pZCAtIDE7CiAgICAJZWxzZSBpZiAoeCA+IHByaW1lc1ttaWRdKQogICAgCQlsb3cgPSBtaWQgKyAxOwogICAgCWVsc2UKICAgIAkJcmV0dXJuIG1pZDsKICAgIH0KICAgIHJldHVybiAtMTsKfQp2b2lkIGdyaWRoYWNrZXZlbihpbnQgaSwgaW50IGosIGludCBuKSB7CglpZiAobWVtbzFbaV1bal0gPT0gdHJ1ZSkKCQlyZXR1cm47CgltZW1vMVtpXVtqXSA9IHRydWU7CgliW2ldW2pdID0gdHJ1ZTsKCWlmIChqKzEgPD0gbi0xICYmIGV2ZW5baV1baisxXSA9PSB0cnVlKSB7CgkJYltpXVtqKzFdID0gdHJ1ZTsKCQlncmlkaGFja2V2ZW4oaSxqKzEsbik7Cgl9CglpZiAoai0xID49IDAgJiYgZXZlbltpXVtqLTFdID09IHRydWUpIHsKCQliW2ldW2otMV0gPSB0cnVlOwoJCWdyaWRoYWNrZXZlbihpLGotMSxuKTsKCX0KCWlmIChpLTEgPj0gMCAmJiBldmVuW2ktMV1bal0gPT0gdHJ1ZSkgewoJCWJbaS0xXVtqXSA9IHRydWU7CgkJZ3JpZGhhY2tldmVuKGktMSxqLG4pOwoJfQoJaWYgKGkrMSA8PSBuLTEgJiYgZXZlbltpKzFdW2pdID09IHRydWUpIHsKCQliW2krMV1bal0gPSB0cnVlOwoJCWdyaWRoYWNrZXZlbihpKzEsaixuKTsKCX0KCXJldHVybjsKfQp2b2lkIGdyaWRoYWNrb2RkKGludCBpLCBpbnQgaiwgaW50IG4pIHsKCWlmIChtZW1vMltpXVtqXSA9PSB0cnVlKQoJCXJldHVybjsKCW1lbW8yW2ldW2pdID0gdHJ1ZTsKCWJbaV1bal0gPSB0cnVlOwoJaWYgKGorMSA8PSBuLTEgJiYgb2RkW2ldW2orMV0gPT0gdHJ1ZSkgewoJCWJbaV1baisxXSA9IHRydWU7CgkJZ3JpZGhhY2tvZGQoaSxqKzEsbik7Cgl9CglpZiAoai0xID49IDAgJiYgb2RkW2ldW2otMV0gPT0gdHJ1ZSkgewoJCWJbaV1bai0xXSA9IHRydWU7CgkJZ3JpZGhhY2tvZGQoaSxqLTEsbik7Cgl9CglpZiAoaS0xID49IDAgJiYgb2RkW2ktMV1bal0gPT0gdHJ1ZSkgewoJCWJbaS0xXVtqXSA9IHRydWU7CgkJZ3JpZGhhY2tvZGQoaS0xLGosbik7Cgl9CglpZiAoaSsxIDw9IG4tMSAmJiBvZGRbaSsxXVtqXSA9PSB0cnVlKSB7CgkJYltpKzFdW2pdID0gdHJ1ZTsKCQlncmlkaGFja29kZChpKzEsaixuKTsKCX0KCXJldHVybjsKfQkJCmlubGluZSB2b2lkIHNjYW4oaW50ICphKSB7CglyZWdpc3RlciBjaGFyIGM9MDsKCXdoaWxlIChjIDwgMzMpCgkJYyA9IGdldGNoYXJfdW5sb2NrZWQoKTsKCSphID0gMDsJCgl3aGlsZSAoYyA+IDMzKSB7CgkJKmEgPSAqYSAqIDEwICsgYyAtICcwJzsKCQljID0gZ2V0Y2hhcl91bmxvY2tlZCgpOwoJfQp9CgppbnQgbWFpbigpewogICAgaW50IGksajsKCiAgICAvKmZpbGwgdGhlIGFycmF5IHdpdGggbmF0dXJhbCBudW1iZXJzKi8KICAgIGZvciAoaT0wO2k8TElNSVQ7aSsrKXsKICAgICAgICBudW1iZXJzW2ldPWkrMjsKICAgIH0KCiAgICAvKnNpZXZlIHRoZSBub24tcHJpbWVzKi8KICAgIGZvciAoaT0wO2k8TElNSVQ7aSsrKXsKICAgICAgICBpZiAobnVtYmVyc1tpXSE9LTEpewogICAgICAgICAgICBmb3IgKGo9MipudW1iZXJzW2ldLTI7ajxMSU1JVDtqKz1udW1iZXJzW2ldKQogICAgICAgICAgICAgICAgbnVtYmVyc1tqXT0tMTsKICAgICAgICB9CiAgICB9CiAgICBqID0gMDsKICAgIGZvciAoaT0wO2k8TElNSVQmJmo8UFJJTUVTO2krKykKICAgICAgICBpZiAobnVtYmVyc1tpXSE9LTEpCiAgICAgICAgICAgIHByaW1lc1tqKytdID0gbnVtYmVyc1tpXTsKCQoJaW50IGxpbWl0ID0gajsKCWludCB0LCBuOwoJbG9uZyBsb25nIGNvdW50OwoJc2NhbigmdCk7Cgl3aGlsZSAodC0tKSB7CgkJc2Nhbigmbik7CgkJZm9yIChpID0gMDsgaSA8IG47IGkrKykgewoJCQlmb3IgKGogPSAwOyBqIDwgbjsgaisrKSB7CgkJCQlzY2FuKCZhW2ldW2pdKTsKCQkJCWJbaV1bal0gPSBmYWxzZTsKCQkJCW1lbW8xW2ldW2pdID0gZmFsc2U7CgkJCQltZW1vMltpXVtqXSA9IGZhbHNlOwoJCQkJZXZlbltpXVtqXSA9IGZhbHNlOwoJCQkJb2RkW2ldW2pdID0gZmFsc2U7CgkJCQlpZiAobnVtYmVyc1thW2ldW2pdLTJdID09IC0xKSB7CgkJCQkJaWYgKGFbaV1bal0gJSAyID09IDApIHsKCQkJCQkJZXZlbltpXVtqXSA9IHRydWU7CgkJCQkJCW9kZFtpXVtqXSA9IGZhbHNlOwoJCQkJCX0KCQkJCQllbHNlIHsKCQkJCQkJb2RkW2ldW2pdID0gdHJ1ZTsKCQkJCQkJZXZlbltpXVtqXSA9IGZhbHNlOwoJCQkJCX0KCQkJCX0KCQkJfQoJCX0KCQljb3VudCA9IDA7CgkJZm9yIChpID0gMDsgaSA8IG47IGkrKykgewoJCQlmb3IgKGogPSAwOyBqIDwgbjsgaisrKSB7CgkJCQlpZiAoYltpXVtqXSAhPSB0cnVlKSB7CgkJCQkJaWYgKG51bWJlcnNbYVtpXVtqXS0yXSAhPSAtMSkgewoJCQkJCQliW2ldW2pdID0gdHJ1ZTsKCQkJCQkJY291bnQgKz0gYlNlYXJjaChhW2ldW2pdLDAsbGltaXQtMSk7CgkJCQkJfQkKCQkJCQllbHNlIGlmIChldmVuW2ldW2pdID09IHRydWUpIHsKCQkJCQkJY291bnQgKz0gKGFbaV1bal0+PjEpOwoJCQkJCQlncmlkaGFja2V2ZW4oaSwgaiwgbik7CgkJCQkJfQoJCQkJCWVsc2UgaWYob2RkW2ldW2pdID09IHRydWUpIHsKCQkJCQkJY291bnQgKz0gKChhW2ldW2pdKzEpPj4xKSArMTsKCQkJCQkJZ3JpZGhhY2tvZGQoaSwgaiwgbik7CgkJCQkJfQoJCQkJfQoJCQl9CgkJfQoJCXByaW50ZigiJWxsZFxuIiwgY291bnQpOwoJfQoJCQoJcmV0dXJuIDA7Cn0=