Гурток

У деякій школі країни Олімпія проводиться гурток з інформатики, в якому займаються N досвідчених програмістів та N новачків. Тренер будує заняття, орієнтуючись на роботу в парі досвідченого учня та новачка. Провівши тренування, тренер визначив ефективність співпраці i-го досвідченого програміста з j-м новачком, що виражається числом a_ij. Загальна ефективність роботи гуртка дорівнює сумарному показнику ефективності співпраці для всіх N пар за умови, що кожен учень працюватиме в парі, причому тільки в одній. Тренер хоче періодично проводити ротації пар, тому його цікавить питання: чи при довільному розбитті на пари ефективність роботи гуртка буде однаковою.

Завдання

Напишіть програму, що за інформацією про ефективність співпраці кожної пари з досвідченого учня та новачка визначатиме, чи ефективність роботи гуртка відрізнятиметься залежно від того, як учнів розбито на пари.

Вхідні дані

Перший рядок вхідного файла містить натуральне число K (1 ≤ K ≤ 50) — кількість тестів у файлі. Далі йде опис Kрізних гуртків: в окремому рядку записано натуральне число N (2 ≤ N ≤ 100) — кількість досвідчених програмістів та новачків у гуртку; потім іде N рядків по N цілих чисел через пропуск: j-те число в i-му рядку дорівнює a_ij (0 ≤ a_ij ≤ 20000) — ефективність роботи в парі i-го досвідченого програміста з j-м новачком.

Вихідні дані

Вихідний файл має містити K чисел, записаних по одному в рядку: i-те з них ((2 ≤ i ≤ K)) — сумарна ефективність i-го гуртка, якщо вона не залежить від розподілу учнів на пари, або -1 в іншому випадку.

Приклади

Оцінювання

Набір тестів складається з 3 блоків, для яких додатково виконуються такі умови:

1. 30 % балів: 2 ≤ N ≤ 10 для всіх гуртків.

2. 20 % балів: 10 < N ≤ 50 для всіх гуртків.

3. 50 % балів: 50 < N ≤ 100 для всіх гуртків.