Comisarul Roman se află în fața unui dispozitiv exploziv constând dintr-o piramidă cu N nivele numerotate de la 1 la N. Fiecare nivel i conține i bombe numerotate de la 1 la i. Notăm bomba j de pe nivelul i cu B[i, j]. Pentru fiecare bombă B[i, j] se cunoaște timpul în secunde T[i, j] de la momentul inițial după care aceasta explodează. Roman trebuie să dezamorseze dispozitivul după următoarele reguli:

• Dezamorsarea unei bombe durează o secundă;
• Pentru a dezamorsa bombă B[i, j] trebuie întâi dezamorsate cele două bombe peste care aceasta este așezată, adică B[i + 1, j] și B[i + 1, j + 1]. Bombele de pe nivelul N nu au bombe dedesubt și deci nu se supun acestei reguli.

Dispozitivul se consideră dezamorsat odată ce toate bombele au fost dezamorsate. Roman nu vrea să se grăbească, așa că ar vrea să știe care este numărul maxim de secunde X astfel încât, dacă ar începe operațiunea de dezamorsare cu o întârziere inițială de X secunde, dispozitivul ar putea fi încă dezamorsat cu succes. Cu alte cuvinte, se cere cel mai mare număr X astfel încât dezamorsarea ar fi posibilă dacă am înlocui numerele T[i, j] cu T[i, j] - X pentru 1 ≤ j ≤ i ≤ N. Este posibil și ca X să fie negativ dacă Roman a ajuns prea târziu la dispozitiv. De exemplu, dacă dezamorsarea nu este posibilă în condițiile date dar ar fi fost posibilă dacă s-ar fi ajuns la fața locului cu o secundă mai devreme, atunci X = -1. Dacă nici cu o secundă mai devreme nu s-ar fi putut, dar s-ar fi putut cu două secunde mai devreme, atunci X = -2, și așa mai departe.

Cerința

Pentru Q teste, date fiind N și valorile T[i, j] pentru 1 ≤ j ≤ i ≤ N, se cere numărul X.

Date de intrare

Prima linie a fişierului de intrare detonator.in conţine Q, reprezentând numărul de teste. Urmează descrierea celor Q teste, fiecare test fiind descris după cum urmează. Prima linie conține numărul întreg N. Următoarele N linii, numerotate în cadrul testului de la 1 la N, conțin numere întregi astfel încât al j-lea număr de pe linia i este T[i, j]. Observați că linia i conține i numere.

Date de ieșire

Fișierul de ieșire detonator.out trebuie să conțină Q linii, reprezentând numărul X pentru fiecare test dat.

Restricții și precizări

• 1 ≤ Q ≤ 5
• 1 ≤ N ≤ 1000
• 1 ≤ T[i, j] ≤ 1.000.000.000 pentru 1 ≤ j ≤ i ≤ N
• Pentru 7 puncte, Valorile T[i, j] pentru 1 ≤ j ≤ i ≤ N sunt egale (toate bombele sunt programate să explodeze în același timp)
• Pentru 13 puncte, N ≤ 5, |X| ≤ 10
• Pentru 9 puncte, N ≤ 5
• Pentru 14 puncte, N ≤ 50, |X| ≤ 10 si T[i, j] ≥ max{T[i + 1, j], T[i + 1, j + 1]} pentru 1 ≤ j ≤ i < N
• Pentru 13 puncte, N ≤ 50, |X| ≤ 10
• Pentru 2 puncte, N ≤ 50
• Pentru 9 puncte, N ≤ 200, |X| ≤ 10
• Pentru 2 puncte, N ≤ 200
• Pentru 19 puncte, N ≤ 500
• Pentru 12 puncte, fără restricţii suplimentare.

Exemplu:

detonator.in

4
2
10
10 10
4
10
7 9
4 6 8
1 3 2 5
3
9
9 9
1 1 1
3
6
5 3
4 4 4

detonator.out

7
0
-2
0

Explicație

Primul test are N = 2, iar cele N • (N + 1) / 2 = 3 bombe toate explodează după 10 secunde. Astfel, Roman poate aștepta maxim 7 secunde după care să înceapă procesul, dezamorsând cele trei bombe după 8, 9 și respectiv 10 secunde.
Al doilea test este ilustrat în figura de mai sus. În acest caz, Roman trebuie să înceapă dezamorsarea imediat, deoarece bomba B_{4, 1} ar exploda după o secundă. Singura ordine de dezamorsare validă este dată de valorile B_{i, j} în ordinea 1, 2, ..., 10.
Al treilea test are trei bombe ce explodează imediat, așa că Roman ar fi trebuit să ajungă cu 2 secunde mai devreme la dispozitiv.