\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 Для кожного тесту у вихідний файл виводиться число, рівне вазі з`їдених комарів.