== include(page="template/taskheader" task_id="carte") ==

Chiar dacă mai sunt câteva zile până la Crăciun, moşul i-a adus deja cadourile lui Georgică, pentru că a fost foarte cuminte. Acesta a găsit sub brad o carte, întitulată "Cartea fără spaţii". După cum îi spune şi numele, cartea conţine cuvinte, care însă nu sunt separate între ele. Astfel, vom spune că ea este formată dintr-un şir de litere mici ale alfabetului englez. Pentru a înţelege mesajul cărţii cât mai bine, Georgică trebuie să separe cuvintele între ele, astfel încât numărul de cuvinte pe care nu le înţelege să fie minim. Georgică înţelege un cuvânt, daca acesta se află în dicţionarul limbii sale.

Chiar dacă mai sunt câteva zile până la Crăciun, moşul i-a adus deja cadourile lui Georgică, pentru că a fost foarte cuminte. Acesta a găsit sub brad o carte, intitulată "Cartea fără spaţii". După cum îi spune şi numele, cartea conţine cuvinte, care însă nu sunt separate între ele. Astfel, vom spune că ea este formată dintr-un şir de litere mici ale alfabetului englez. Pentru a înţelege mesajul cărţii cât mai bine, Georgică trebuie să separe cuvintele între ele, astfel încât numărul de cuvinte pe care nu le înţelege să fie minim. Georgică înţelege un cuvânt, daca acesta se află în dicţionarul limbii sale.

Dându-se numărul de teste $T$, iar pentru fiecare test conţinutul cărţii, numărul de cuvinte ale dicţionarului $N$ şi cele $N$ cuvinte din dicţionar, să se spună care este numărul minim de cuvinte pe care Georgică nu le inţelege după ce separă cuvintele între ele într-un mod convenabil.

h2. Restricţii
* $T = 10$

* $1 ≤ N ≤ 5.000$
* $Cartea nu conţine mai mult de 50.000 caractere$
* $Cuvintele din dicţionar vor avea cel mult 50.000 caractere$

* $1 ≤ N ≤ 1.000$
* $Cartea nu conţine mai mult de 5.000 caractere$
* $Cuvintele din dicţionar vor avea cel mult 5.000 caractere$

h2. Exemplu