ELCS - Easy Longest Common Substring

no tags 

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

hide comments
Kinan Sarmini: 2010-05-18 23:42:38

Does that mean that the total number of characters in all strings doesn't exceed 500000?

Reply: Yes.( <=500000 ) :)

One more thing, the input format and the example don't match, which one is correct?

Reply: Sorry . The example is right.

Last edit: 2010-05-18 12:20:45

Added by:刘启鹏
Date:2010-05-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:my own problem