Problem title
Difficulty
Avg time to solve

Angle Between Hour Hand And Minute Hand
Easy
15 mins
3 Divisors
Moderate
25 mins
Maximum Length of Chain
Moderate
15 mins
Distinct Paths
Moderate
20 mins
Rearrange words in a sentence
Easy
15 mins
Count Valid Pairs
Moderate
25 mins
Largest cake
Moderate
10 mins
Word Boggle
Ninja
--
Evaluate Division
Moderate
15 mins
Disjoint Intervals
Moderate
30 mins
2

# Longest Common Prefix

Difficulty: MEDIUM
Avg. time to solve
30 min
Success Rate
70%

Problem Statement

#### Vidit comes to you and asks you to write a program that calculates the number of steps the algorithm uses to find each of the Q query words.

##### Input Format:
`````` The first line contains an integer N (1 ≤ N ≤ 30000), the number of words in the database.
Each of the following N lines contains a single word from the database. The words are given in the order the algorithm compares them to a query word. All words in the database will be distinct.
The following line contains an integer Q (1 ≤ Q ≤ 30000), the number of words searched for.
Each of the following Q lines contains a single query word.
All words in the input will be strings of less than 30 lowercase letters of the English alphabet.
``````
##### Constraints:
`````` Time Limit: 2 seconds
``````
##### Output Format:
`````` Output one integer per line for each query word, the number of steps the algorithm uses when searching for the word.
``````

#### Sample Input 1:

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

#### Sample Output 1:

``````8
29
14
``````

#### Explanation:

``````In the first test case, the number of steps to search for the word "krampus" is 8 because the algorithm only needs to compare its first letter to each word in the database.
When searching for the word "malnar", we need three steps for each of the first three words, and four steps for each of the remaining five words, for a total of 29 steps.
To find the word "majmun" we use a total of 14 steps. For the first word in the database, we have six successful comparisons and one step in which we determine that the word "majmunica" is longer than the query word. For the second word, we also have six successful comparisons and a final step in which it is established that the words are equal. After finding the word, the algorithm terminates with great joy
``````
Console