bcast

$N$ calculatoare, numerotate de la $1$ la $N$, sunt interconectate într-o reţea. Calculatorul $1$ deţine nişte informaţii pe care doreşte să le transmită tuturor celorlalte calculatoare (acest tip de transmisie de informaţii este cunoscut sub numele de broadcast). Pentru aceasta, programul care rulează pe calculatorul $1$ trebuie să stabilească o strategie inteligentă de transmitere a informaţiilor, astfel încât acestea să ajungă la toate celelalte calculatoare într-un timp cât mai scurt. Oricare două calculatoare pot comunica între ele şi se cunoaşte durata de transmisie a informaţiilor de la orice calculator $i$ la orice calculator $j$ (durata transmisiei de la $i$ la $j$ poate fi diferită de durata transmisiei de la $j$ la $i$). Din momentul în care un calculator $i$ a primit informaţiile, acesta le poate transmite mai departe altor calculatoare. La orice moment de timp, un calculator poate transmite informaţii numai unui singur alt calculator. Aşadar, dacă un calculator $i$ doreşte să transmită informaţii calculatoarelor $j$ şi $k$, el va trebui să transmită întâi informaţiile calculatorului $j$, iar după ce acestea au fost recepţionate (după o durată de timp egală cu durata transmisiei de la $i$ la $j$), ele pot fi transmise apoi calculatorului $k$. În mod evident, transmisiile între două perechi diferite de calculatoare se pot realiza în paralel. Durata de timp după care informaţiile ajung la toate calculatoarele este cel mai mare moment de timp la care un calculator primeşte informaţiile (considerând că procesul de transmitere a informaţiilor începe la momentul $0$).

Cerinţă

Determinaţi durata de timp minimă (corespunzătoare unei strategii inteligente de broadcast) după care informaţiile ajung la toate calculatoarele.

Date de intrare

Fişierul de intrare bcast.in conţine pe prima linie numărul natural $T$, reprezentând numărul de seturi de date de test. În continuare, urmează descrierea celor $T$ seturi. Prima linie din cadrul fiecărui set de test conţine numărul natural $N$, reprezentând numărul de calculatoare. Următoarele $N$ linii conţin câte $N$ numere întregi, separate prin câte un spaţiu. Al $j$-lea număr de pe a $i$-a dintre aceste linii conţine durata de transmisie a informaţiilor de la calculatorul $i$ la calculatorul $j$. Durata transmisiei de la un calculator la el însuşi va fi întotdeauna egală cu $0$.

Date de ieșire

În fişierul bcast.out veţi afişa $T$ linii, câte una pentru fiecare set de date de test. Pe linia $i$ va fi scris un număr natural $T_{min}$ reprezentând durata minimă după care informaţiile pot ajunge la toate calculatoarele pentru al $i$-lea set de test din fişierul de intrare.

Restricții și precizări

• $1 \leq T \leq 10$;
• $1 \leq N \leq 12$;
• $0 \leq$ Durata de transmisie a informaţiilor de la un calculator $i$ la un calculator $j \leq 10 \ 000$

Exemplu

bcast.in

2
4
0 4 2 1
4 0 16 13
7 8 0 9
10 11 3 0
2
0 0
10 0

bcast.out

5
0

Explicație

În cazul primului set de test, la momentul $0$, calculatorul $1$ începe să trimită informaţiile calculatorului $4$ (transmisia durează până la momentul $1$). La momentul $1$, calculatorul $1$ începe să transmită informaţiile calculatorului $2$ (transmisia durează până la momentul $5$), iar calculatorul $4$ începe să transmită informaţiile calculatorului $3$ (transmisia durează până la momentul $4$). Momentele de timp la care cele $4$ calculatoare află informaţiile sunt : $0$, $5$, $4$ şi $1$.
În cazul celui de-al doilea set de test, la momentul $0$ calculatorul $1$ începe să transmită informaţiile calculatorului $2$, iar transmisia se termină tot la momentul $0$.