AlgoLiga 2018

Jaś bawił się ostatnio królem od szachów i szachownicą. Ustawił króla na pewnym konkretnym polu na szachownicy N x N i zaczął wykonywać nim wszystkie możliwe kombinacje K ruchów. Po każdej kombinacji kładł króla na początkowo wybrane pole oraz zaczynał kolejną, inną kombinację K ruchów. Król w jego zabawie może wykonywać dokładnie takie same ruchy jak król w szachach. Jaś po pewnym czasie wykonał wszystkie możliwe kombinacje K ruchów, każdą dokładnie raz. Dla każdego pola spisał ile kombinacji zostało zakończonych na tym polu, położył kartkę ze spisanymi liczbami obok szachownicy i poszedł programować, bo właśnie miała się zacząć kolejna runda AlgoLigi. Dwa dni później, już po zakończeniu rundy AlgoLigi, Jaś przypomniał sobie o swojej zabawie. Znalazł kartkę ze spisanymi liczbami i gdy ją ujrzał naszły go dwa pytania. Jaka była początkowa pozycja króla, oraz ile ruchów miały kombinacje które wykonywał ? Pomóż mu, znajdź odpowiedź na te pytania!

Wejście

W pierwszej linii liczba zestawów danych T (1 ≤ T ≤ 10).

W pierwszej linii każdego zestawu danych znajduje się jedna liczba N (2 ≤ N ≤ 500).

W każdej z kolejnych N linii każdego zestawu danych znajduje się po N liczb. Każda liczba opisuje ilość kombinacji K ruchów, które zakończyły się na tym polu. Liczby te są nie większe niż 10¹⁸.

Wyjście

Dla każdego zestawu danych wypisz "K a b", 3 liczby całkowite oznaczające kolejno liczbę ruchów w kombinacjach, wiersz w którym znajdował się król na początku każdej kombinacji oraz kolumnę w której znajdował się król na początku każdej kombinacji.

Przykład

Wejście:
2
2
7 7 
6 7 
3
48 64 48 
70 96 74 
48 64 48 
Wyjście:
3 2 1
4 2 3