Crazy Frog
Many of you might be familiar with the songs about the adventures of the little frog, Crazy Frog. This time, the lively creature has decided to grab a snack, but even this simple task has turned into a game. The game board is a square grid divided into N*N cells (N <= 50). Each cell contains a mosquito with a weight of a_ij, where the weight is a natural number not exceeding 50. Here, i represents the row number and j the column number. As the frog hops from cell to cell, it eats the mosquitoes. The rules of the game are as follows: in each column, the frog can eat at most one mosquito. Each time a mosquito is eaten, the row number from which it was eaten is recorded. By the end of the game, the sum of these row numbers must exactly equal N. Note that if mosquitoes are eaten from the same row multiple times, the row number is counted each time.
Your task is to determine the maximum total weight of mosquitoes that the frog can eat while adhering to these rules.
Input
The first line of input specifies the number of test cases. For each test case, the first line contains the number N. The following N lines each contain N integers a(i, j), separated by spaces.
Output
For each test case, output a single number representing the maximum weight of the mosquitoes eaten.