\includegraphics{https://static.e-olymp.com/content/bc/bc42ea914976e0a6e21f2fbbb43cb5fa777ddc9e.gif} Многие, вероятно, слышали песни о приключениях лягушонка Crazy Frog. На этот раз неугомонное милое создание решило подкрепиться, но даже такое простое действие решило выполнить в виде игры. Итак, в каждой клетке квадратного игрового поля, разбитого на \textbf{N}*\textbf{N} (\textbf{N} <= \textbf{50}) клеток, находится комар весом \textbf{a_ij} (вес комара -- натуральное число <= \textbf{50}), \textbf{i} - номер строки, \textbf{j} - номер столбца. Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы - в каждом столбце можно съесть не более одного комара. Всякий раз при съедании комара запоминаем номер строки, откуда съеден комар, и сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна \textbf{N}. Учтите, если из какой-то строки съедено несколько комаров, то номер данной строки участвует в суммировании более одного раза. Определите максимальный вес комаров, который можно съесть при следовании приведённым правилам. \InputFile Первая строка входа содержит количество тестов. Первая строка каждого теста содержит число \textbf{N}. Следующие \textbf{N} строк содержат по \textbf{N} чисел \textbf{a}(\textbf{i}, \textbf{j}), разделенных пробелами. \OutputFile Для каждого теста в выходной файл выводится число, равное весу съеденных комаров.