Símanúmer

Kristín hefur risið til metorða innan Rannsóknardeildar Lögreglunnar í Reykjavík undanfarin ár, einna helst vegna færni sinnar í tölvunarfræði, og er orðinn einn helsti rannsakandi deildarinnar. Við rannsóknir mála vinnur hún oftast með vitnum og hefur hún tekið eftir því, í vinnu sinni, að vitni muna símanúmer mjög illa. Flest vitni muna bara fyrstu stafina í símanúmerum.

Þau símanúmer sem vitnin gefa upp eru oftar en ekki lykillinn að lausn sakamálanna, en það kerfi sem lögreglan notar við að fara í gegnum símanúmerin er ekki skilvirkt. Hópur lögregluþjóna fer yfir öll skráð símanúmer og tínir til þau símanúmer sem byrja á þeim tölustöfum sem vitnin gefa upp.

Kristín, verandi tölvunarfræðingur, veit að hægt er að gera leitina töluvert skilvirkari, en er mjög upptekin og biður því ykkur um að útfæra leitina fyrir sig. Forritið á að geta tekið við upphafi símanúmers, sem við köllum fyrirspurn, frá vitni og segir svo til um hversu mörg símanúmer byrja á þeirri fyrirspurn.

Inntak

Fyrsta lína inntaksins inniheldur heiltölu $N$ sem segir til um fjölda símanúmera í safninu sem lögreglan hefur yfir að ráða. Næstu $N$ línur innihalda símanúmer safnsins, eitt símanúmer í hverri línu. Engin tvö símanúmer eru eins, og hvert þeirra samanstendur af $7$ tölustöfum. Næsta lína inniheldur heiltölu $Q$ sem segir til um fjölda fyrirspurna. Næstu $Q$ línur innihalda fyrirspurnirnar, ein fyrirspurn í hverri línu. Hver fyrirspurn samanstendur af $1$ til $7$ tölustöfum.

Úttak

Skrifið út eina línu fyrir sérhverja fyrirspurn með fjölda símanúmera í safninu sem byrja á þeirri fyrirspurn.

Stigagjöf

Lausnin mun verða prófuð á miserfiðum inntaksgögnum, og er gögnunum skipt í hópa eins og sýnt er í töflunni að neðan. Lausnin mun svo fá stig eftir því hvaða hópar eru leystir.

Hópur

Stig

Inntaksstærð

Önnur skilyrði

1

5

$N=1$, $Q=1$

Hver fyrirspurn inniheldur nákvæmlega $3$ tölustafi

2

5

$N = 1$, $Q=1$

 

3

15

$N \leq 100$, $Q \leq 100$

Hver fyrirspurn inniheldur nákvæmlega $3$ tölustafi

4

20

$N \leq 100$, $Q \leq 100$

 

5

25

$N \leq 10^5$, $Q \leq 10^5$

Hver fyrirspurn inniheldur nákvæmlega $3$ tölustafi

6

30

$N \leq 10^5$, $Q \leq 10^5$

 
Sample Input 1 Sample Output 1
4
8245477
9917762
9871234
8247713
5
824
9
99177
8245477
565
2
2
1
1
0