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 integers a and b. You must answer the length of the ELCS of the a-th string and b-th string.

Input

First line consists one integer N.

Next N lines consist N strings.

Next line consists one integer Q.

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

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

100% of the test data: 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