Domácí kolo

B: Ponožky

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Vašek se rozhodl, že si dá vyprat všechny svoje barevné ponožky. Naházel je tedy do pračky a pračku zapnul. Po skončení praní ponožky postupně po jedné tahal z pračky. Zajímalo by ho, jestli všechny svoje ponožky dokáže popárovat a kolik lichých ponožek mu zbyde. Předpokládejte, že Vašek chce najednou nosit pouze dvě ponožky stejné barvy (nerozlišuje levou a pravou).

Máme N ponožek a každá z nich má barvu označenou číslem od 1 do K. Stejnou barvu může mít i víc než jeden pár ponožek. Představte si, že všechny ponožky leží na jedné hromadě a vy můžete vždy dvě ponožky stejné barvy vzít a spárovat (odebrat z hromady). Zajímá nás, kolik na hromadě zbyde ponožek takových, že je už nelze nijak popárovat.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit.

Pro každý problém dostanete na prvním řádku dvě čísla: N udává počet ponožek, K je počet různých barev ponožek. Na dalším řádku následuje N kladných celých čísel z rozsahu od 1 do K oddělených mezerou. Každé z těchto čísel udává barvu jedné Vaškovy ponožky.

Tvar výstupu

Pro každý problém vypište na samostatný řádek číslo udávající počet "lichých" ponožek (těch, které se nedají popárovat).

Lehká verze

  • T ≤ 10
  • N ≤ 100
  • K ≤ 100

Těžká verze

  • T ≤ 10
  • N ≤ 100 000
  • K ≤ 100

Ukázkový vstup

2
4 2
2 1 1 2
8 4
3 2 2 4 3 2 2 3

Ukázkový výstup

0
2

Vysvětlení ukázkového vstupu a výstupu

V prvním případě vidíme, že ponožky barvy 1 i ponožky barvy 2 jsou dvě. Snadno tedy vytvoříme dva páry a nic nám nezbyde.

V druhém případě máme dva páry ponožek barvy 2, jeden pár a jednu lichou ponožku barvy 3 a jednu ponožku barvy 4. Zbydou nám proto 2 ponožky, jedna barvy 3 a jedna 4.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)