Kahden pelaajan pelissä pakassa on $n$ korttia, jotka jaetaan puoliksi pelaajille. Korttien arvot ovat $1,2,\dots,n$ ja $n$ on aina parillinen.

Peli muodostuu $n/2$ kierroksesta, joissa kumpikin pelaaja laittaa pöytään jonkin jäljellä olevista korteistaan. Se pelaaja, jonka kortin arvo on suurempi, saa pisteen kierrokselta.

Tiedät, että vastustajasi pelaa aina korttinsa suurimmasta pienimpään. Montako pistettä saat, jos pelaat optimaalisesti?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $t$: testien määrä.

Jokaisessa testissä ensimmäisellä rivillä on kokonaisluku $n$ ja toisella rivillä on $n/2$ kokonaislukua: sinulla olevat kortit.

Tuloste

Tulosta jokaisesta testistä suurin pistemäärä, jonka voit saavuttaa.

Esimerkki

Syöte:

3
6
2 4 5
2
1
4
1 3

Tuloste:

2
0
1

Osatehtävä 1 (23 pistettä)

• $1 \le t \le 1000$
• $1 \le n \le 10$

Osatehtävä 2 (77 pistettä)

• $1 \le t \le 1000$
• $1 \le n \le 100$