#include <bits/stdc++.h>
using namespace std;

// general
#define ll long long
#define pb push_back
#define pob pop_back
#define f first
#define s second
#define mp make_pair
#define PI 3.14159265
//#define fastio

//--------------//

// IO funcs
#ifdef fastio

#define SC(x) scanf("%c", &x)
#define SD(x) scanf("%d", &x)
#define SLL(x) scanf("%lld", &x)
#define SS(x) scanf("%s", x)

#define PC(x) printf("%c", x)
#define PD(x) printf("%d", x)
#define PLL(x) printf("%lld", x)
#define PS(x) printf("%s", x)

#define gc getchar_unlocked

void scanint(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}

#else // fastio

#define SC(x) cin >> x
#define SD(x) cin >> x
#define SLL(x) cin >> x
#define SS(x) cin >> x

#define PC(x) cout << (x)
#define PD(x) cout << (x)
#define PLL(x) cout << (x)
#define PS(x) cout << (x)

#endif

//----fastio-end---//

// funcs
#define swap(a, b) a ^= b ^= a ^= b
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
//----------------//

// statements
#define LP(i, ii, jj) for (int i = (ii); i < (jj); i++)
#define LPR(i, ii, jj) for (int i = (ii); i >= (jj); i--)
//----------------//

// DS
#define Vi vector<int>
#define Pii pair<int, int>
#define Piii pair<int, Pii>
#define Plli pair<ll, int>
#define Pll2 pair<ll, ll>
#define Mii map<int, int>
//----------------//

//#define MATHUTIL

#ifdef MATHUTIL
#define MOD 1000000007

ll powmod(ll b, ll e, ll m)
{
    b %= m;
    ll r = 1;
    while (e > 0)
    {
        if (e & 1)
            r = (r * b) % m;
        b = (b * b) % m;
        e >>= 1;
    }
    return r;
}

ll gcd(ll u, ll v)
{
    ll t;
    while (v)
    {
        t = u;
        u = v;
        v = t % v;
    }
    return u < 0 ? -u : u;
}

int gcd(int u, int v)
{
    int t;
    while (v)
    {
        t = u;
        u = v;
        v = t % v;
    }
    return u < 0 ? -u : u;
}

int get_count0(ll x)
{
    int r = 0;
    while (x % 10 == 0)
    {
        x /= 10;
        r++;
    }
    return r;
}

int sodHelp(ll x)
{
    int r = 0;
    while (x)
    {
        r += (x % 10);
        x /= 10;
    }
    return r;
}

int sod(ll x)
{
    while (x >= 10)
    {
        x = sodHelp(x);
    }
    return x;
}

#endif // MATHUTIL

#ifdef NCR
int C[31][31] = {0};

void PreNCR(int n)
{
    C[0][0] = 1;

    for (int i = 1; i <= n; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            // nCj = (n-1)Cj + (n-1)C(j-1);
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }
}

#endif // NCR

//#define TRIE
#ifdef TRIE

int GetI(char x)
{
    if (x == ' ')
        return 52;
    if (x == '?')
        return 53;
    if (x >= 'a' && x <= 'z')
        return x - 'a' + 26;
    return x - 'A';
}

struct TNode
{
    TNode *next[26] = {0};
};

void AddToTrie(string& s, TNode *trie)
{
    for (int i = 0; i < s.size(); i++)
    {
        char c = s[i];
        int x = c-'A';
        if (trie->next[x] == NULL)
        {
            trie->next[x] = new TNode();
        }
        trie = trie->next[x];
    }
}

int GetCount(char s[], TNode *trie)
{
    for (int i = 0; s[i] != '\n' && s[i] != '\0'; i++)
    {
        int x = GetI(s[i]);
        if (trie->next[x] == NULL)
        {
            return 0;
        }
        trie = trie->next[x];
    }
    return 0;
}

#endif // TRIE

//#define PRIME
#ifdef PRIME
vector<ll> Primes;

void InitPrimes()
{
    bool prime[100001];
    memset(prime, true, sizeof(prime));

    for (int p = 2; p * p <= 50000; p++)
    {
        if (prime[p])
        {
            for (int i = p * 2; i <= 50000; i += p)
                prime[i] = false;
        }
    }

    for (int p = 2; p <= 50000; p++)
        if (prime[p])
            Primes.pb(p);
}

vector<int> Facts;

void Factorize(int v)
{
    Facts.clear();
    int temp = v;
    for (int i = 0; Primes[i] * Primes[i] <= temp && v > 1; i++)
    {
        if (v % Primes[i] == 0)
        {
            Facts.pb(Primes[i]);
            while (v % Primes[i] == 0)
                v /= Primes[i];
        }
    }
    if (v != 1)
        Facts.pb(v);
}

#endif // PRIME

//#define BIT
#ifdef BIT

int BITree[100010];
bool BITDone[100010];
int lgn;
void BITUpdate(int x, int n, int delta)
{
    x++;
    for (; x <= n; x += x & -x)
        BITree[x] += delta;
}
int BITQuery(int x, int n)
{
    x++;
    int sum = 0;
    for (; x > 0; x -= x & -x)
        sum += BITree[x];
    return sum;
}
bool BITDiffQuery(int s, int e, int n)
{
    return BITQuery(s,n) == BITQuery(e,n);
}

#endif // BIT

#ifdef TEMPCODE
string s;
bool done[100];
int dp[100];

int fillDP(int i)
{
    if (done[i])
        return dp[i];

    char c = s[i];
    dp[i] = 0;
    done[i] = 1;

    if (c == 'e')
    {
        LP(j, i + 1, s.size())
        {
            if (s[j] == 'f')
            {
                dp[j] = 1;
                done[j] = 1;
                dp[i]++;
            }
        }
    }
    char next;
    switch (c)
    {
    case 'c':
        next = 'h';
    case 'h':
        next = 'e';
    }

    LP(j, i + 1, s.size())
    {
        if (next == s[j])
        {
            dp[i] += fillDP(j);
        }
    }
    return dp[i];
}
#endif // TEMPCODE

    //#define AVLTREE

#ifdef AVLTREE
struct Node
{
    int key;
    int weight = 1;
    struct Node *left = NULL;
    struct Node *right = NULL;
    int height = 1;
};

int Height(Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}

int Weight(Node *N)
{
    if (N == NULL)
        return 0;
    return N->weight;
}

Node *NewNode(int key)
{
    Node *node = new Node();
    node->key = key;
    return node;
}

Node *RightRotate(Node *y)
{
    Node *x = y->left;
    Node *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->weight -= x->weight;
    y->weight += (T2 != NULL ? T2->weight : 0);
    x->weight -= (T2 != NULL ? T2->weight : 0);
    x->weight += y->weight;

    y->height = max(Height(y->left), Height(y->right)) + 1;
    x->height = max(Height(x->left), Height(x->right)) + 1;

    return x;
}

struct Node *LeftRotate(struct Node *x)
{
    struct Node *y = x->right;
    struct Node *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->weight -= y->weight;
    x->weight += (T2 != NULL ? T2->weight : 0);
    y->weight -= (T2 != NULL ? T2->weight : 0);
    y->weight += x->weight;

    x->height = max(Height(x->left), Height(x->right)) + 1;
    y->height = max(Height(y->left), Height(y->right)) + 1;

    return y;
}

int GetBalance(Node *N)
{
    if (N == NULL)
        return 0;
    return Height(N->left) - Height(N->right);
}

Node *Insert(Node *node, int key)
{
    if (node == NULL)
        return NewNode(key);

    node->weight++;
    if (key < node->key)
        node->left = Insert(node->left, key);
    else if (key > node->key)
        node->right = Insert(node->right, key);
    else
        return node;

    node->height = 1 + max(Height(node->left), Height(node->right));

    int balance = GetBalance(node);

    if (balance > 1 && key < node->left->key)
        return RightRotate(node);

    if (balance < -1 && key > node->right->key)
        return LeftRotate(node);

    if (balance > 1 && key > node->left->key)
    {
        node->left = LeftRotate(node->left);
        return RightRotate(node);
    }

    if (balance < -1 && key < node->right->key)
    {
        node->right = RightRotate(node->right);
        return LeftRotate(node);
    }

    return node;
}

Node *MinValueNode(Node *node)
{
    Node *current = node;

    while (current->left != NULL)
        current = current->left;

    return current;
}

Node *DeleteNode(Node *root, int key)
{
    if (root == NULL)
        return root;

    root->weight--;
    if (key < root->key)
        root->left = DeleteNode(root->left, key);
    else if (key > root->key)
        root->right = DeleteNode(root->right, key);
    else
    {
        if ((root->left == NULL) || (root->right == NULL))
        {
            Node *temp = root->left ? root->left : root->right;
            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else
                *root = *temp;
            free(temp);
        }
        else
        {
            Node *temp = MinValueNode(root->right);
            root->key = temp->key;
            root->right = DeleteNode(root->right, temp->key);
        }
    }
    if (root == NULL)
        return root;

    root->height = 1 + max(Height(root->left), Height(root->right));

    int balance = GetBalance(root);

    if (balance > 1 && GetBalance(root->left) >= 0)
        return RightRotate(root);

    if (balance > 1 && GetBalance(root->left) < 0)
    {
        root->left = LeftRotate(root->left);
        return RightRotate(root);
    }

    if (balance < -1 && GetBalance(root->right) <= 0)
        return LeftRotate(root);

    if (balance < -1 && GetBalance(root->right) > 0)
    {
        root->right = RightRotate(root->right);
        return LeftRotate(root);
    }

    return root;
}

int GetIndex(Node *node, int key)
{
    if (node == NULL)
        return 0;

    if (key < node->key)
        return GetIndex(node->left, key);
    else if (key > node->key)
        return Weight(node->left) + 1 + GetIndex(node->right, key);
    return Weight(node->left) + 1;
}

#endif // AVLTREE

//#define MINST

#ifdef MINST
int MinVal(int x, int y) { return (x < y)? x: y; }
int Mid(int s, int e) { return s + (e -s)/2; }

int GetMinHelp(int *st, int ss, int se, int qs, int qe, int i)
{
    if (qs <= ss && qe >= se)
        return st[i];
 
    if (se < qs || ss > qe)
        return INT_MAX;
 
    int mid = Mid(ss, se);
    return MinVal(GetMinHelp(st, ss, mid, qs, qe, 2*i+1),
                  GetMinHelp(st, mid+1, se, qs, qe, 2*i+2));
}
 
int GetMin(int *st, int n, int qs, int qe)
{
    return GetMinHelp(st, 0, n-1, qs, qe, 0);
}

int PopulateSTHelp(int arr[], int ss, int se, int *st, int si)
{
    if (ss == se)
    {
        st[si] = arr[ss];
        return arr[ss];
    }

    int mid = Mid(ss, se);
    st[si] =  MinVal(PopulateSTHelp(arr, ss, mid, st, si*2+1),
                     PopulateSTHelp(arr, mid+1, se, st, si*2+2));
    return st[si];
}

int* PopulateST(int arr[], int n)
{
    int x = ceil(log2(n)); 
    int sz = 2*(int)pow(2, x); 
 
    int *st = new int[sz];
    PopulateSTHelp(arr, 0, n-1, st, 0);
    return st;
}

#endif // LAZYST

#define NMAX 1010

bool conn[NMAX][NMAX];
ll graph[NMAX][NMAX];
int n;

void AddFact(int i, vector<int>& v, bool done[])
{
        LP(j,0,n)
        {
            if(graph[i][j] && !done[j])
            {
                done[j] = 1;
                v.pb(j);
                AddFact(j, v, done);
            }
        }
}


vector<vector<int> > gfacts;
void GFactorize()
{
    bool done[NMAX] = {0};
    LP(i,0,n)
    {
        if(!done[i])
        {
            vector<int> v;
            v.pb(i);
            LP(j,0,n)
            {
                if(conn[i][j])
                {
                    v.pb(j);
                    done[j] = 1;
                }
            }
            gfacts.pb(v);
        }
    }
}

inline void Solve(int TC)
{
    SD(n);
    int b[NMAX][NMAX];
    ll co = 0;
    LP(i,0,n)
    {
        LP(j,0,n)
        {
            SLL(graph[i][j]);
            if(graph[i][j])
            {
                co+=1;
            }
        }
    }
    LP(i,0,n)
    {
        LP(j,0,n)
        {
            graph[i][j] = graph[j][i] = max(graph[i][j], graph[j][i]);
        }
    }

    LP(k,0,n)
    {
        LP(i,0,n)
        {
            LP(j,0,n)
            {
                if(graph[i][k] && graph[k][j] && i!=j)
                {
                    graph[i][j] = 1;
                }
            }
        }
    }

    ll ans = 0;
    LP(i,0,n)
    {
        LP(j,0,n)
        {
            ans+=graph[i][j];
            //cout<<graph[i][j]<<" ";
        }
        //cout<<endl;
    }
    PLL(ans-co);
    PC('\n');
    return;

    GFactorize();

    //cout<<gfacts.size()<<endl;
    LP(ii,0,gfacts.size())
    {
        ll cur = gfacts[ii].size();
        ans+=(cur*(cur-1));
    }
    PLL(ans-co);
    PC('\n');
    return;
    //cout<<"fans "<<ans<<endl;
    bool done[1001] = {0};
    int lastma = 0;
    map<pair<int, ll>, int> :: iterator it;
    LP(ii, 1, n)
    {
        map<pair<int, ll>, int> m;
        LP(i,0,n)
        {
            if(!done[i])
            {
                int ma = 0;
                LP(j,0,n) 
                {
                    if(!done[j] && i!=j)
                    {
                        ma = max(ma, b[i][j]);
                    }
                }
                ma = max(lastma, ma);
                ll rem = 0;
                LP(j,0,n)
                {
                    if(!done[j] && i!=j)
                    {
                        rem += (ma-b[i][j]);
                    }
                }
                m[mp(ma,2*rem)] = i;
            }
        }
        it = m.begin();
        done[(*it).s] = 1;
        ans+=((*it).f.s);
        lastma = (*it).f.f;
        //cout<<"sans "<<(*it).s<<" "<<(*it).f.f<<endl;
    }
    PLL(ans);
    PC('\n');
}

int main()
{
    int t = 1;
    //InitFact();
    //InitPrimes();
    SD(t);
    LP(i, 0, t)
    {
        Solve(i + 1);
    }
    return 0;
}