Mátrix

Készítsen programot, amely a billentyűzetről egy kvadratikus mátrix sorainak számát, valamint a mátrix elemeit olvassa be. A program határozza meg és írja a szabványos kimenetre azt az értéket, amit úgy kapunk, hogy előbb a második bemenetsor elemeit az alábbi ábrán (5x5-ös mátrix példáján) látható módon elhelyezzük a mátrixban, majd az így kapott mátrix sorait azok sorösszege szerinti csökkenő sorba rendezzük (úgy, hogy az esetlegesen azonos sorösszegű sorok egymáshoz viszonyított sorrendje ne változzon!), végül pedig összegezzük az így átrendezett mátrix mellékátlójában található értékeket.

A fenti jobb oldali ábra azt mutatja be, hogy miképp kell az [1..25] zárt intervallum értékeit elhelyezni egy 5x5-ös mátrixban. A bal alsó ábrán az látszik, hogy összegezzük a sorokat, míg a jobb alsón a mátrix már átrendezett elemeit sorait, és a mellékátló összegzésének az eredményét láthatjuk.

A bemenet első sora egy 1 ≤ k ≤ 100 pozitív egész érték, amely a tesztesetek számát jelenti. Minden teszteset pontosan két sorból áll: az első sorban egyetlen, szintén 1 és 100 közötti n egész (a kvadratikus mátrix mérete), míg a másodikban pontosan n² egész (a kvadratikus mátrix elemei) helyezkedik el. A mátrix elemeit egymástól szóköz karakterek választják el. A kimenet tesztesetenként egy sorban egyetlen egész értéket, a fentiek értelmében kitöltött és átrendezett mátrix mellékátlóban lévő elemeinek összegét tartalmazza.

Példa bemenet

1. 3
2. 5
3. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
4. 3
5. 69 94 81 41 9 98 39 4 0
6. 2
7. 1 0 0 1

Példa kimenet

1. 65
2. 148
3. 0