In this problem, a string only consists of lowercase letters.

Substring, is a consecutive sequence of characters occurrences at least once in a string.

Common substring means a substring of two strings.

After getting TLE on LCS and LCS2, lqp18_31 felt really depressed. So he came up with an interesting idea. He want to modify the definition of LCS and call it ELCS.

ELCS: for two given strings s1[0…n-1] and s2[0…m-1], the ELCS of them is a string p[0…k-1]  k<=min(n,m) so that s1[i]=s2[i]=p[i] ( for 0<=i<k ) and s1[k]!=s2[k] or k==n or k==m .

Now your task is easy.

You are given N strings and Q queries.

Each query consists two intergers a and b. You must answer the length of the ELCS of the a-th string and b-th string.

Input

Firtst line consists one interger N.

Next N lines consist N strings.

Next one line consists one interger Q.

Next Q lines consist two intergers a and b. (0<=a,b<N)

30% of the testdata : N<=100 Q<=10000 length(string[i])<=100

100% of the testdata : the number of total characters<=500000 N<=100000 Q<=100000

Output

Q lines. Each line consists the length of the ELCS of the a-th string and b-th string

Example

Input:
5
dy
ljq
lqp
ws
jzt
3
0 1
1 2
0 2
Output:
0
1
0