Гурток#7391

Гурток

1 секунда

64 мегабайти

Дуже легка

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

Завдання

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

Вхідні дані

У першому рядку задано ціле число $K$ ( $1 \leq K \leq 50$ 1 \leq K \leq 50) — кількість тестів.

Кожен тест описується рядком з цілим числом $N$ ( $2 \leq N \leq 100$ 2 \leq N \leq 100) — кількість досвідчених програмістів і новачків. Далі слідує $N$ рядків по $N$ цілих чисел: $j$ -те число в $i$ -му рядку — це $a_{ij}$ a_{ij} ( $0 \leq a_{ij} \leq 20000$ 0 \leq a_{ij} \leq 20000), ефективність роботи $i$ -го досвідченого програміста з $j$ -м новачком.

Вихідні дані

Для кожного тесту виведіть одне число у окремому рядку: загальну ефективність гуртка, якщо вона однакова для будь-якого розбиття на пари, інакше виведіть $- 1$ .

Приклади

Приклад 1

Оцінювання

Набір тестів поділений на три блоки з додатковими обмеженнями:

30% балів: $2 \leq N \leq 10$ 2 \leq N \leq 10.
20% балів: $10 < N \leq 50$ 10 < N \leq 50.
50% балів: $50 < N \leq 100$ 50 < N \leq 100.