Tudor is teaching Jason how to be productive!

One day, Tudor decides that Jason isn't taking his work seriously enough, and installs some software to monitor Jason's monitor. Jason is now only allowed to type strings which are in a whitelist.

Jason has already written some string and wishes to turn it into another string. In a single second, he can either insert a character, delete a character, or change some character in the string into another one. Note that, per the whitelist, Jason must only ever have strings in the whitelist on his monitor during any given second.

Input Specification

The input starts with a single integer $N$ $(1\le N\le 500)$, the number of words in the whitelist.

$N$ lines follow, each containing a single string of only uppercase letters. Each string has length at most 500. Each of these strings will be distinct.

After that, a line with a single integer $Q$ $(1\le Q\le {10}^5)$ follows.

After that, $Q$ lines follow with two positive integers between $1$ and $N$, the first one being the index of the word Jason starts out with and the second one being the index of the word Jason wants.

Output Specification

For each query line, output the minimum number of seconds Jason needs to convert the first word to the second one. Output -1 if it is impossible for him to perform the conversion.

Sample Data ZIP

Click here for ZIP.

Sample Input

3
BIG
BUG
DAMAGE
2
1 2
1 3

Sample Output

1
-1