Baza

Το μεγαλύτερο κοινό πρόθεμα δύο λέξεων είναι η μεγαλύτερη λέξη με την οποία ξεκινούν και οι δύο λέξεις. Για παράδειγμα, το μεγαλύτερο κοινό πρόθεμα των λέξεων «identity» και «idealistic» είναι η λέξη «ide».
Μια βάση δεδομένων περιέχει ~N~ λέξεις.
Ο αλγόριθμος για την αναζήτηση μιας λέξης ~W~, που ρωτήθηκε, στη βάση δεδομένων είναι πρωτόγονος. Συγκρίνει τη λέξη ~W~ μία προς μία με κάθε λέξη στη βάση δεδομένων. Δύο λέξεις συγκρίνονται γράμμα προς γράμμα μέχρι να βρεθεί ένα γράμμα στο οποίο διαφέρουν ή μέχρι να φτάσουμε στο τέλος μιας από τις λέξεις (μετά διαπιστώνεται είτε ότι οι λέξεις είναι ίσες είτε ότι η μία είναι μεγαλύτερη από την άλλη). Όταν ο αλγόριθμος βρει τη λέξη ~W~ στη βάσης δεδομένων, τερματίζεται.
Η ανάλυση του αλγόριθμου δείχνει ότι ο αριθμός των βημάτων που απαιτούνται για την εύρεση μιας λέξης ~W~ είναι ίσος με τον αριθμό των λέξεων με τις οποίες συγκρίνεται η ~W~, συν το άθροισμα των μηκών των μεγαλύτερων κοινών προθεμάτων του ~W~ και καθεμίας από τις λέξεις με τις οποίες συγκρίθηκε.
Γράψτε ένα πρόγραμμα που να υπολογίζει τον αριθμό των βημάτων που χρησιμοποιεί ο αλγόριθμος για να βρει καθένα από τα ~Q~ ερωτήματα λέξεων.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N\;(1 \le N \le 30\,000)~, τον αριθμό των λέξεων στη βάση δεδομένων.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει μία λέξη από τη βάση δεδομένων. Οι λέξεις δίνονται με τη σειρά που ο αλγόριθμος τις συγκρίνει με μια λέξη ερωτήματος. Όλες οι λέξεις στη βάση δεδομένων θα είναι διακριτές.
Η ακόλουθη γραμμή περιέχει έναν ακέραιο αριθμό ~Q\;(1 \le Q \; 30\,000)~, τον αριθμό των λέξεων που αναζητήθηκαν.
Κάθε μία από τις ακόλουθες ~Q~ γραμμές περιέχει μία λέξη ερωτήματος.
Όλες οι λέξεις στην είσοδο θα είναι συμβολοσειρές με λιγότερα από ~30~ πεζά γράμματα του αγγλικού αλφαβήτου.

Έξοδος

Τυπώστε έναν ακέραιο αριθμό ανά γραμμή για κάθε λέξη ερωτήματος, τον αριθμό των βημάτων που χρησιμοποιεί ο αλγόριθμος κατά την αναζήτηση της λέξης.

Παραδείγματα

input

5
hobotnica
robot
hobi
hobit
robi
4
robi
hobi
hobit
rakija

output

12
10
16
7

input

8
majmunica
majmun
majka
malina
malinska
malo
maleni
malesnica
3
krampus
malnar
majmun

output

8
29
14

Επεξήγηση του 2ου παραδείγματος:

Ο αριθμός των βημάτων για την αναζήτηση της λέξης "krampus" είναι ~8~, επειδή ο αλγόριθμος χρειάζεται μόνο να συγκρίνει το πρώτο του γράμμα με κάθε λέξη στη βάση δεδομένων.
Κατά την αναζήτηση της λέξης "malnar", χρειαζόμαστε τρία βήματα για καθεμία από τις τρεις πρώτες λέξεις και τέσσερα βήματα για καθεμία από τις υπόλοιπες πέντε λέξεις, για συνολικά ~29~ βήματα.
Για να βρούμε τη λέξη "majmun" χρησιμοποιούμε συνολικά ~14~ βήματα. Για την πρώτη λέξη στη βάση δεδομένων, έχουμε έξι επιτυχημένες συγκρίσεις και ένα βήμα στο οποίο προσδιορίζουμε ότι η λέξη "majmunica" είναι μεγαλύτερη από τη λέξη ερωτήματος. Για τη δεύτερη λέξη, έχουμε επίσης έξι επιτυχημένες συγκρίσεις και ένα τελικό βήμα στο οποίο διαπιστώνεται ότι οι λέξεις είναι ίσες. Μετά την εύρεση της λέξης, ο αλγόριθμος τερματίζει με μεγάλη χαρά.