Рабочее место участника

Многие, вероятно, слышали песни про приключения лягушонка Crazy Frog. На этот раз неугомонное милое создание решило подкрепиться, но даже такое простое действие решило выполнить в виде игры. Итак, в каждой клетке квадратного игрового поля, разбитого на `N*N` (`N\ ≤\ 50`) клеток, находится комар весом `a_{ij}` (вес комара – натуральное число ≤ 50), `i` – номер строки, `j` – номер столбца. Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы – в каждом столбце можно съесть не более одного комара. Всякий раз при съедании комара запоминаем номер строки, откуда съеден комар, и сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна `N`. Учтите, если из какой-то строки съедено несколько комаров, то номер данной строки участвует в суммировании более одного раза.

Определите максимальный вес комаров, который можно съесть при следовании приведённым правилам.

Первая строка входа содержит количество тестов. Первая строка каждого теста содержит число `N`. Следующие `N` строк содержат по `N` чисел `a_{ij}`, разделенных пробелами.

Для каждого теста в выходной файл выводится число, равное весу съеденных комаров.

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

14
19