As we all know, Harry Porter learns magic at Hogwarts School. However, learning magical knowledge alone is insufficient to become a great magician. Sometimes, Harry also has to gain knowledge from other certain subjects, such as language, mathematics, English, and even algorithm.
Today, Harry is on his biological class, his teacher is doing experiment with DNA right now. But the clever teacher faces a difficult problem. He has lots of genes. Every time he picks gene a and gene b. If he want to connect gene a and gene b, he should calculate the length of longest part that the gene a¡¯s suffix and gene b¡¯s prefix can overlap together. For example gene a is "AAT" and gene b is "ATT", then the longest common part is "AT", so the answer is 2. And can you solve this difficult problem for him?
Input
They are sever test cases, you should process to the end of file.
For each test case, there are two integers n and m ($1 \leq n \leq 100000, 1 \leq m \leq 100000$)on the first line, indicate the number of genes and the number of queries.
The next following n line, each line contains a non-empty string composed by characters 'A' , 'T' , 'C' , 'G'. The sum of all the characters is less than 100000.
Then the next following m line, each line contains two integers a and b($1 \leq a, b \leq n$), indicate the query.
Output
For each query, you should output one line that contains an integer indicate the length of longest part that the gene a¡¯s suffix and gene b¡¯s prefix can overlap together.
