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, the number of testcases. The first line of each case will contain two integers N and Q. Then each of the next N lines will contain a string, ith line will contain the string Ai. Then the folowing Q lines will contain two integers each L and R, as described in the statement.

1 ≤ T≤ 15
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
1 ≤ L ≤ R ≤ N
1 ≤ |Ai| ≤ 105
Sum of length over all N strings per case will be ≤ 106

Subtask 1 (10 points):
1 ≤ T≤ 15, 1 ≤ N ≤ 10, 1 ≤ Q ≤ 100, 1 ≤ L ≤ R ≤ N, 1 ≤ |Ai| ≤ 20Sum of length over all N strings per case will be ≤ 100

Subtask 2 (30 points):
1 ≤ T≤ 15, 1 ≤ N ≤ 100, 1 ≤ Q ≤ 10000, 1 ≤ L ≤ R ≤ N, 1 ≤ |Ai| ≤ 4100Sum of length over all N strings per case will be ≤ 10000

Subtask 3 (60 points): Original constraints.

Output

For each query, print 1 line, ith line is the answer to the ith 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

Dataset is huge, use faster I/O methods.