Boekenkasten

Beschrijving

Berend is bibliothecaris. Hij beheert de boeken van de universiteitsbibliotheek in Preh Fiks. Vanwege de gestage groei van de collectie is het huidige gebouw te klein geworden, dus de bibliotheek gaat verhuizen.

Het Probleem

Van deze gelegenheid wil Berend gebruik maken om de boeken op een andere manier te verdelen over de nieuwe kasten. Hij wil op elke plank boeken hebben staan, waarvan de naam dezelfde prefix heeft. Maar de grootste prefix van alle boeken op een plank mag niet voorkomen als begin van zo'n prefix op iedere andere plank, zodat boeken gemakkelijk op prefix te vinden zijn.

Voorbeeld: als `Verwachting' en `Verwarring' op één plank staan (prefix verwa), mogen `Vermoedens' en `Verlakkerij' niet samen op één andere plank staan (prefix ver, begin van verwa), maar `Vroomheid' en `Vrede' wel (prefix vr). Nou is er altijd te weinig geld, dus hoe minder kasten Berend nodig heeft, hoe beter.

De Invoer

De eerste regel bevat een getal dat de hoeveelheid runs aangeeft. Dan volgt per run:

De Uitvoer

Per run één getal: de minimale hoeveelheid kasten die Berend nodig heeft.

Voorbeeld

Bij de invoer
2
1
2
2
past
precies
1
2
5
past
pijnlijk
genoeg
niet
precies
hoort de uitvoer
1
5