K. Sam-Oh, the funny coach
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Sam-Oh is teaching a course for his university contestants on how to be funny (instead of teaching them useful algorithms for SCPC). The course consists of $$$m$$$ parts, each part contains 26 jokes where a joke is represented as a small Latin English letter. But Sam-Oh is depressed as the contestants aren't funny at all! they only learn one joke of each part out of the 26 jokes!!

So, after the course ends, each contestant is learned $$$m$$$ jokes. In other words, the learned jokes of each person can be represented as a string of length $$$m$$$ consisting of small Latin English letters. Not only this! Sam-Oh found out that these strings are sorted in non-decreasing order! To overcome his depression, Sam-Oh will make the funny dual event. In this event, he will choose $$$Q$$$ pairs of contestants and test their fun compatibility by finding the number of shared jokes at each index $$$i$$$ of the two strings. More formally, let $$$s$$$ be the string of jokes of the first contestant and $$$t$$$ the string of the other one, and count the number of indices $$$i$$$ such that: $$$s_i = t_i$$$

Sam-Oh is busy telling jokes and making other coaches happy (he thinks so) so he will give you the pairs of contestants and asks you to find the results.

Note: Every string is sorted, The array of strings isn't sorted necessarily.

Input

The first line contains two integers $$$n, m$$$ $$$( 2 \le n \cdot m \le 5 \cdot 10^{5} )$$$ — the number of contestants and the number of jokes respectively.

The next $$$n$$$ lines contain string $$$s_i$$$ $$$( | s_i | = m )$$$ — the learned jokes by the $$$i$$$-th contestant, sorted in non-decreasing order.

The third line contains one integer $$$Q$$$ $$$( 1 \le Q \le 10^{6} )$$$ — the number of tests Sam-Oh will do.

The next $$$Q$$$ lines contains two integers $$$p_{1_i}, p_{2_i}$$$ $$$( 1 \le p_{1_i}, p_{2_i}\le n)$$$ — The pair of the $$$i$$$-th test.

It's guaranteed that there are at least two contestants in the university.

Output

Output $$$Q$$$ lines, the $$$i$$$-th line should contain the $$$i$$$-th test result.

Example
Input
3 4
aaab
aabb
abbc
5
1 1
2 2
1 2
2 3
1 3
Output
4
4
3
2
1