Crazy frog
Багато з вас, напевно, чули пісні про пригоди жабенятка Crazy Frog. На цей раз невгамовне миле створіння вирішило підкріпитись, але навіть таку просту дію вирішило виконати у вигляді гри. Отже, у кожній клітинці квадратного ігрового поля, розбитого на N*N (N <= 50) клітин, знаходиться комар вагою a_ij (вага комара – натуральне число <= 50), i - номер рядка, j - номер стовбчика. Жабеня, стрибаючи з клітини на клітину, поїдає комарів. Правила гри такі - у кожному стовбчику можна з'їсти не більше одного комара. Кожен раз при поїданні комара запам'ятовуємо номер рядка, у якому з'їдено комара, і сума номерів рядків, у яких були з'їдені комари, у кінці гри повинна бути точно рівна N. Врахуйте, якщо із-за якогось рядка з'їдено декількі комарів, то номер даного рядка приймає участь у додаванні більше одного разу.
Визначіть максимальну вагу комарів, яку можна з'їсти додтримуючись наведених правил.
Вхідні дані
Перший рядок входу містить кількість тестів. Перший рядок кожного тесту містить число N. наступні N рядків містять по N чисел a(i, j), відокремлених пропусками.
Вихідні дані
Для кожного тесту у вихідний файл виводиться число, рівне вазі з'їдених комарів.