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.

- \(S^{'}\) is both the suffix of \(S_{i}\) and \(S_{j}\)
- 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.

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\)).

提交代码