说明

小黑被无限掳走了！风息为了将小黑重新拉回妖精的阵营，决定孤身前往妖灵会馆准备与无限决一死战（qiangmao）！

但是无限很强，所以风息在和无限对上之前，他需要先通过“豪夺”获得足够多的别的妖精的能力用来对付无限。

现在已知，从风息到无限和小黑的位置之间的妖精们的排列可以看做是一个一共N层的正三角形，第i层有i只妖精，每只妖精的能力都可以被看成是一个整数，数字越大说明该妖精的能力越强。

风息在每一层只能夺取一只妖精的能力，并且因为他想快点找到小黑所以他决定每层只夺取一只妖精的能力，且只能走和他当前位置直接相连的两个位置（即假设风息现在在( i , j )，那他下一步只能走（ i+1 , j+1 ），或者( i+1 , j )）。风息希望能在和无限开打之前获得足够多的能力。

fc是无限大人的迷妹，她想知道无限大人到底要面对一个多强的风息，但是她实在太菜了，所以她向你求助，请你输出当风息对上无限的时候，他当前的能力的总和。（ps.默认风息最开始的时候的能力为0）

输入格式

第一行给出样例总数 T ( T < = 50 )

第二行给出层数 N ( N < = 1000 )

后面 N 行给出每层妖精们的能力值。

输出格式

输出一行风息在和无限对上的时候他所有的能力值。

样例

1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

30

提示

风息和无限和罗小黑他们的位置并不在输入的三角形中。