Crazy Frog#405
Many of you have probably heard the songs about the adventures of the little frog, Crazy Frog. This time, the energetic creature decided to have a snack, but even this simple task was turned into a game. So, on a square game board of size N \times N (N \leq 50), in each cell there is a mosquito weighing a_{ij} (a natural number ), where is the row number and is the column number. The frog jumps from cell to cell, eating mosquitoes. The rules of the game are as follows: in each column, at most one mosquito can be eaten. Every time a mosquito is eaten, the row number is recorded, and by the end of the game, the sum of all row numbers where mosquitoes were eaten must be exactly . Note that if mosquitoes from the same row are eaten multiple times, that row number is counted each time.
Determine the maximum total weight of mosquitoes that can be eaten while following these rules.
The first line of input contains the number of test cases. For each test, the first line contains the number . The next lines each contain integers a_{ij}, separated by spaces.
For each test case, print one number equal to the total weight of the mosquitoes eaten.
Example 1