import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static void main
(String[] args
) { //code
Scanner in
= new Scanner
(System.
in); int t = in.nextInt();
for(int i=0;i<t;i++){
int n = in.nextInt();
int a[][]= new int[n][n];
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
a[j][k]=in.nextInt();
int h = Mat(a,n);
}
}
public static int Mat(int [][] a, int n){
/*or(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print(a[i][j]+" ");
}
System.out.println();
}
System.out.println();*/
for(int i=1;i<n;i++){
for(int j=0;j<n;j++){
if(j==0){
a[i][j] = Max(a[i][j]+a[i-1][j],a[i][j]+a[i-1][j+1]);
}
else if(j==n-1){
a[i][j]=Max(a[i][j]+a[i-1][j],a[i][j]+a[i-1][j-1]);
}
else a[i][j] = Max(a[i][j]+a[i-1][j],a[i][j]+a[i-1][j+1],a[i][j]+a[i-1][j-1]);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
System.
out.
print(a
[i
][j
]+" "); }
int max=0;
for(int i=0;i<n;i++){
if(max<a[n-1][i]) max=a[n-1][i];
}
/*for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print(a[i][j]+" ");
}
System.out.println();
}*/
return max;
}
public static int Max(int a,int b){
return a>b?a:b;
}
public static int Max(int a, int b, int c){
if(a>b && a>c) return a;
else if(b>a && b>c) return b;
else return c;
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBHRkcgewoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHsKCQkvL2NvZGUKCQlTY2FubmVyIGluID0gbmV3IFNjYW5uZXIoU3lzdGVtLmluKTsKCQlpbnQgdCA9IGluLm5leHRJbnQoKTsKCQlmb3IoaW50IGk9MDtpPHQ7aSsrKXsKCQkgICAgaW50IG4gPSBpbi5uZXh0SW50KCk7CgkJICAgIGludCBhW11bXT0gbmV3IGludFtuXVtuXTsKCQkgICAgZm9yKGludCBqPTA7ajxuO2orKykKCQkgICAgICAgIGZvcihpbnQgaz0wO2s8bjtrKyspCgkJICAgICAgICAgICAgYVtqXVtrXT1pbi5uZXh0SW50KCk7CgkJICAgICAgICAgICAgCgkJICAgIGludCBoID0gTWF0KGEsbik7ICAgICAgCgkJICAgIFN5c3RlbS5vdXQucHJpbnRsbihoKTsKCQl9Cgl9CglwdWJsaWMgc3RhdGljIGludCBNYXQoaW50IFtdW10gYSwgaW50IG4pewoJICAgIC8qb3IoaW50IGk9MDtpPG47aSsrKXsKCSAgICAgICAgZm9yKGludCBqPTA7ajxuO2orKyl7CgkgICAgICAgICAgU3lzdGVtLm91dC5wcmludChhW2ldW2pdKyIgIik7CgkgICAgICB9CgkgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oKTsKCSAgICB9CgkgICAgU3lzdGVtLm91dC5wcmludGxuKCk7Ki8KCSAgICBmb3IoaW50IGk9MTtpPG47aSsrKXsKCSAgICAgICAgZm9yKGludCBqPTA7ajxuO2orKyl7CgkgICAgICAgICAgICBpZihqPT0wKXsKCSAgICAgICAgICAgICAgICBhW2ldW2pdID0gTWF4KGFbaV1bal0rYVtpLTFdW2pdLGFbaV1bal0rYVtpLTFdW2orMV0pOwoJICAgICAgICAgICAgfQoJICAgICAgICAgICAgZWxzZSBpZihqPT1uLTEpewoJICAgICAgICAgICAgICAgIGFbaV1bal09TWF4KGFbaV1bal0rYVtpLTFdW2pdLGFbaV1bal0rYVtpLTFdW2otMV0pOwoJICAgICAgICAgICAgfQoJICAgICAgICAgICAgZWxzZSBhW2ldW2pdID0gTWF4KGFbaV1bal0rYVtpLTFdW2pdLGFbaV1bal0rYVtpLTFdW2orMV0sYVtpXVtqXSthW2ktMV1bai0xXSk7CgkgICAgICAgIH0KCSAgICB9CgkgICAgZm9yKGludCBpPTA7aTxuO2krKyl7CgkgICAgCWZvcihpbnQgaj0wO2o8bjtqKyspCgkgICAgCQlTeXN0ZW0ub3V0LnByaW50KGFbaV1bal0rIiAiKTsKCSAgICAJCVN5c3RlbS5vdXQucHJpbnRsbigpOwoJICAgIH0KCSAgICBpbnQgbWF4PTA7CgkgICAgZm9yKGludCBpPTA7aTxuO2krKyl7CgkgICAgICAgIGlmKG1heDxhW24tMV1baV0pIG1heD1hW24tMV1baV07CgkgICAgfQoJICAgIC8qZm9yKGludCBpPTA7aTxuO2krKyl7CgkgICAgICAgIGZvcihpbnQgaj0wO2o8bjtqKyspewoJICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnQoYVtpXVtqXSsiICIpOwoJICAgICAgfQoJICAgICAgU3lzdGVtLm91dC5wcmludGxuKCk7CgkgICAgfSovCgkgICAgICAKCSAgICByZXR1cm4gbWF4OwoJfQoJcHVibGljIHN0YXRpYyBpbnQgTWF4KGludCBhLGludCBiKXsKCSAgICByZXR1cm4gYT5iP2E6YjsKCX0KCXB1YmxpYyBzdGF0aWMgaW50IE1heChpbnQgYSwgaW50IGIsIGludCBjKXsKCSAgICBpZihhPmIgJiYgYT5jKSByZXR1cm4gYTsKCSAgICBlbHNlIGlmKGI+YSAmJiBiPmMpIHJldHVybiBiOwoJICAgIGVsc2UgcmV0dXJuIGM7Cgl9Cn0=