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.

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, i^th line will contain the string A_i. Then the folowing Q lines will contain two integers each L and R, as described in the statement.

1 ≤ T≤ 15
1 ≤ N ≤ 10⁵
1 ≤ Q ≤ 10⁵
1 ≤ L ≤ R ≤ N
1 ≤ |A_i| ≤ 10⁵
Sum of length over all N strings per case will be ≤ 10⁶

Subtask 1 (10 points):
1 ≤ T≤ 15, 1 ≤ N ≤ 10, 1 ≤ Q ≤ 100, 1 ≤ L ≤ R ≤ N, 1 ≤ |A_i| ≤ 20
Sum 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 ≤ |A_i| ≤ 4100
Sum of length over all N strings per case will be ≤ 10000

Subtask 3 (60 points): Original constraints.

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

Dataset is huge, use faster I/O methods.