8. Yucatán na polia!

Adam, okrem toho, že je nadšeným záhradníkom, má aj ďalšiu pasiu: cestovanie časom¹. Naposledy² sa vybral do starovekého Yucatánu. Moc si to ale nepremyslel, bol veľmi rýchlo zajatý a už by bol dávno³ aj obetovaný, keby nepoužil svoje presvedčovacie schopnosti a technické zručnosti.

V skratke – ukázal Mayom kombajny, tí okamžite pochopili, že sa jedná o výrazne lepšiu zábavku, než ľudské obety, a pustili sa do novej aktivitky plnou parou.

Ale také poľnohospodárstvo nie je len tak! Na poliach rastú rôzne druhy kukurice, ktoré Mayovia nechcú pomiešať, takže na jeden ťah kombajnom možno zožať len jeden druh kukurice. Navyše, čím viac kukurice sa naraz zožne, tým šťastnejší bohovia budú. Kukuricu, pochopiteľne, treba nakoniec zožať celú. Lenže ako? Zas sa obrátili na Adama (ten ešte nestihol použiť svoj časomanipulátor) aby im s tým pomohol, inak sa vrátia ku svojím tradičným praktikám! Zúfalý Adam vytesal svoj problém do steny pyramídy, ktorú ste nedávno objavili. Popisuje tam polia, ktoré potrebujú Mayovia zožať, a prosí vás, aby ste problém vyriešili a pomohli mu prežiť. Teraz je to na vás! Pošlite Adamovi rýchlo riešenie, inak sa už z minulosti nevráti a KSP stránka schátra a zomrie!

Úloha

Kukurica rastie na \(n\) políčkach v jednom dlhom poli. Kombajn vie naraz zožať súvislú časť poľa na ktorom rastie tá istá odroda kukurice. Ak je medzi dvoma úsekmi rovnakej odrody už zožatý priestor, kombajn ním vie prejsť a zožať úseky naraz. Mayovia sú presvedčení, že ak naraz zožnú \(k\) políčok kukurice (počítajú sa len tie, ktoré naozaj zožnú, nie tie, čo prejdú naprázdno), zväčší to šťastie bohov o \(k^2\) jednotiek.

Po každom zožatí úseku vedia Mayovia kombajn premiestniť na ľubovočné políčko predtým, než budú znova žať.

Zistite ako by mali Mayovia žať, aby dosiahli maximálne šťastie bohov a Adam sa mohol vrátiť ku programovaniu Trojsten webov!

Formát vstupu

Na prvom riadku je číslo \(t \leq 200\) – počet polí kukurice.

Ďalej nasleduje \(2t\) riadkov popisujúcich polia kukurice.

Popis každého poľa má dva riadky: na prvom je celé číslo \(1\leq n\leq 200\) – počet políčok kukurice na danom poli. Na druhom riadku je pole popísané \(n\) medzerami oddelenými číslami, ktoré označujú odrody kukurice. Môžete predpokladať, že všetky odrody sú celé čísla medzi \(1\) a \(n\).

Existujú štyri testovacie sady. Platia v nich nasledovné obmedzenia:

Súčet dĺžok všetkých polí v žiadnom vstupe nepresiahne \(2000\).

Formát výstupu

Pre každé pole na vstupe najskôr vypíšte dve čísla oddelené medzerou: najväčšie množstvo šťastia, ktoré vedia bohom zabezpečiť z tohto poľa, a \(k\) – počet žatí kombajnom ktoré na to potrebujú.

Na ďalších \(k\) riadkoch vypíšte popisy jednotlivých žatí kombajnom: dve medzerami oddelené čísla – prvé a posledné zožaté políčko v danom žatí (políčka číslujeme od \(1\)). Každé žatie kombajnom by malo zožať aspoň jedno ešte nezožaté políčko kukurice (Mayovia nežnú naprázdno).

Žatia vypíšte v poradí v akom by ich Mayovia mali vykonať.

Príklad

Input:

2
5
1 1 3 3 1
3
1 2 3

Output:

13 2
3 4
1 5
3 3
1 1
2 2
3 3

Pre prvé pole vieme pri prvom žatí zožať \(2\) políčka, v druhom \(3\). Všimnite si, že pri druhom žatí kombajn prejde cez už zožaté políčka. Pre druhé pole nemáme veľmi na výber, z každého druhu kukurice existuje presne jedno políčko.