Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3995
PreSuffix

Time Limit: 4 Seconds      Memory Limit: 262144 KB

We define a string of length \(l\) as an array \(S[1..l]\). All the elements within it belongs to a finite set \(\sum=\{a,b,...,z\}\).

Let \(\text{Prefix}(S,i)=S[1..i]\) be one prefix of \(S\) with a length of \(i\).

Similarly, \(\text{Suffix}(S,j)=S[j..l]\) denotes one \(S\)'s suffix of length \(l-j+1\).

Now DreamGrid gives you a string multi-set \(\{S_{n}\}\) with the cardinality of \(n\), and \(q\) not so hard tasks:

For every task, you will receive two integers \(i, j\) (\(i \ne j\)) denoting the \(i\)-th and the \(j\)-th string in the aforementioned multi-set. You have to calculate the longest string \(S^{'}\) which satisfies the following two conditions at the same time.

  1. \(S^{'}\) is both the suffix of \(S_{i}\) and \(S_{j}\)
  2. There exists at least one string \(S_{k}\in\{S_{n}\}\) that \(S^{'}\) is the prefix of \(S_{k}\). Let the number of such strings be \(|\{S_{k}\}|\) (Obviously, \(\{S_{k}\}\), which is also a multi-set, is a subset of \(\{S_{n}\}\)).

If such \(S^{'}\) doesn't exist, you have to print a character 'N'(without quotes). Otherwise your program should print \(|\{S_{k}\}|\) in one line.

Input

There are about 10 test cases.

For every test case, the first line contains an integer \(n\) (\( 1 \le n \le 10^5\)).

The next \(n\) lines each contains a lowercased string \(S_{i}\). We guarantee that \(1 \le \sum_{i=1}^{n}|S_{i}|\le 5\times 10^5\) and each string is not empty.

The next line contains an integer \(q\) (\(1 \le q \le 10^5\)).

And the final \(q\) lines each contains two integers \(i, j\) (\(1 \le i, j \le n\), \(i \ne j\)).

Output

For every query, print the answer as the description narrates.

Sample Input

3
ab
cb
de
2
1 2
2 3
7
xabcd
yabcd
cdo
cdp
cdq
cdr
abcdz
1
1 2
3
aa
aa
aa
1
1 3

Sample Output

N
N
1
3

Author: TANG, Xiaohu
Source: ZOJ Monthly, January 2018
Submit    Status