#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int d[][],a[][];

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         int n;

         scanf("%d",&n);

         memset(d,,sizeof(d));

         for(int i = ;i<=n;i++)

             for(int j = ;j<=i;j++) scanf("%d",&a[i][j]);

         for(int i = n;i>=;i--){

             for(int j = ;j<=i;j++)

             d[i][j] = max(d[i+][j],d[i+][j+]) + a[i][j];

         }

         printf("%d\n",d[][]);

     }

     return ;

 }

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int g[][];

 int d[];

 int n;

 struct node{

     int x,y;

 }a[maxn];

 int dp(int i){

     int& ans = d[i];

     if(ans > ) return ans;

     ans = ;

     for(int j = ;j <= n;j++)

     if(g[i][j]) ans = max(ans,dp(j) + );

     return ans;

 }

 int work(){

     int res = -;

     for(int i = ;i <= n;i++) res = max(res,dp(i));

     return res;

 }

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         scanf("%d",&n);

         for(int i = ;i <= n;i++) scanf("%d %d",&a[i].x,&a[i].y);

         memset(g,,sizeof(g));

         memset(d,,sizeof(d));

         for(int i = ;i <= n;i++){

             for(int j = ;j <= n;j++){

                 if((a[i].x > a[j].x && a[i].y > a[j].y) || (a[i].x > a[j].y && a[i].y > a[j].x ))

                 g[i][j] = ;

             }

         }

         printf("%d\n",work());

     }

     return ;

 }