Welcome to ZOJ
 Problem Sets 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.

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