Palindrome and Queries

You'll be given an array $A$ of $N$ strings containing lowercase English letters only and $Q$ queries. In each query, you have to find the length of the longest palindromic substring which appears in at least $L$ strings and at most $R$ strings. If there is no such palindromic substring, print 0.

A palindrome is a word which reads the same backward and forward, such as “madam”, “abba” etc. A substring is a string of character(s) that is contained in another string. For example, “abc” has 6 substrings: “a”, “ab”, “abc”, “b”, “bc”, “c”.

A palindromic substring is a substring which reads the same backward and forward. For example, “taka” has 4 unique palindromic substrings: “t”, “a”, “k”, “aka”.

Input

There will be multiple testcases. The first line of the input will contain an integer $T$ ($1 ≤ T≤ 15$), the number of testcases. The first line of each case will contain two integers $N$ ($1 ≤ N ≤ 10^5$) and $Q$ ($1 ≤ Q ≤ 10^5$). Then each of the next $N$ lines will contain a string, $i$-th line will contain the string $A_i$ ($1 ≤ |A_i| ≤ 10^5$). Then the following $Q$ lines will contain two integers each $L$ and $R$ ($1 ≤ L ≤ R ≤ N$), as described in the statement.

Sum of length over all $N$ strings per case will be $≤ 10^6$.

Output

For each query, print 1 line, $i$-th line is the answer to the $i$-th query.

Sample

1
3 6
aaac
aaabbbbbb
abbaaa
1 1
1 2
1 3
2 2
2 3
3 3

6
6
6
2
3
3

Data set is huge, use faster I/O methods.