#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

const int infinity = 200;
int **tab, *d, v, w, vertexes, temp = 0;
void Display();
void CreateTable()
{
    tab = new int *[vertexes];
    d = new int[vertexes];
}

void ReadData()
{
    for (int i = 0; i < vertexes; i++)
    {
        tab[i] = new int[vertexes];
        for (int j = 0; j < vertexes; j++)
        {
            cin >> v;
            if (v != 0) { tab[i][j] = v; }
            else { tab[i][j] = infinity; }
        }
    }
}

void BellmanFord()
{
    for (int i = 0; i < vertexes; i++) { d[i] = infinity; }
    d[0] = 0;

    for (int k = 0; k < vertexes -1  ; k++)
    {
        for (int i = 0 ; i < vertexes; i++)
        {
            for (int j = 0; j < vertexes; j++)
            {
                if (d[i] + tab[i][j] < d[j])
                    d[j] = d[i] + tab[i][j];
            }
        }
        Display();
        cout << endl;
    }
}
void DeleteTable()
{
    for (int i = 0; i < vertexes; i++)
        delete[] tab[i];
    delete[] tab;
    delete[] d;
    vertexes = 0;
}

void Display()
{
    for (int i = 0; i < vertexes; i++)
    {
        if (d[i] < infinity) { cout << d[i]; }
        else { cout << 0 ; }
    }
}

int main()
{
    int test = 0;
    cin >> test;
    for (int l = 0; l < test; l++)
    {
        cin >> vertexes;
        CreateTable();
        ReadData();
        BellmanFord();
        DeleteTable();
    }
    system("PAUSE");
    return 0;
}