Maksymalna suma

To zadanie pochodzi z Codeforces. Tam też znajdują się testy do zadania.
Jeśli Twoje rozwiązanie zostanie pozytywnie ocenione na tamtych testach, należy wysłać tu zgłoszenie wypisujące "Zrobione".

Limit pamięci: 512 MB

Mamy daną macierz nxn. Należy znaleźć podzbiór pól macierzy, że jego suma jest możliwie największa, a żadne dwa pola nie stykają się (nawet rogami).

Wejście

W pierwszym wierszu znajduje się liczba testów t (t <= 100).
Każdy test składa się z liczby n (n <= 16). Następnie podana jest macierz w formie n wierszów po n liczb (wszystkie liczby są z zakresu [1, 1000]).

Wyjście

Wypisz t wierszy, po jednym na każdy test. W każdym wierszu wypisz największą możliwą sumę, jaką da się uzyskać dla tej macierzy.

Przykład

Wejście:
2
2
4 7
2 9
3
1 2 3
4 5 6
7 8 9

Wyjscie:
9
20