Database String Query Step Count

Given a database containing \(N\) strings, define the common prefix of two strings as the longest substring starting from the beginning that both strings share. For example, the common prefix of identity and idealistic is ide.

The query algorithm for a string \(W\) in the database works as follows: it compares \(W\) with each string in the database one by one. For each comparison, it compares the characters of the strings sequentially until a mismatch is encountered or one of the strings ends. After the character-by-character comparison, a final comparison is made to check whether the lengths of the two strings are equal. Once the algorithm finds \(W\) in the database, it halts.

The total number of steps taken to find \(W\) is defined as the number of strings compared plus the sum of the lengths of the common prefixes between \(W\) and every string it is compared with.

You are given \(Q\) query strings. For each query string, compute the total number of steps required by the algorithm to find the string in the database.

Note: Pay special attention to the unusually stringent memory constraints of this problem.

inputFormat

The input begins with a line containing an integer \(N\), the number of strings in the database.

Each of the next \(N\) lines contains a non-empty string.

The following line contains an integer \(Q\), the number of query strings.

Each of the next \(Q\) lines contains a query string \(W\). It is guaranteed that every query string exists in the database.

outputFormat

For each query, output a single line containing the total number of steps required to locate the query string in the database.

sample

3
identity
idealistic
ideal
1
idealistic

15