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

Input	Output
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.