1641：F Frog Castle

Today, the frog prince is sure to inspect the work within the castle, the castle has n layers, as the pyramid shape, only one room of the top and down respectively, 2, 3... , the bottom have n room.

Due to the architecture design of the castle, each room can only reach the next layer with the serial number of the room, or one more than number of the room, and now the frog prince from the top, down to inspect. In advance, the frog prince has already known the number of people in each under room, he wants to know how many staff that he can inspect mostly.

The first line, enter a number T, showed the layer number of the castle;

The next T lines, each line has N numbers showed the i-th layer the number of staff in the 1~N-th room.

(0 <T < 1000，0<N<100)