Lyndon Substring

A string $w$ is a Lyndon word if $w$ is lexicographically smaller than any of its cyclic rotations.

The longest Lyndon substring of a string $s$ is the longest substring of $s$ that is a Lyndon word.

Chiaki has $n$ strings $s_1, s_2, \dots, s_n$. She has some queries. For a pair $(i, j)$, find the length of the longest Lyndon substring of the string $s_i s_j$.

There are multiple test cases. The first line of input contains an integer $T$, the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$), the number of strings and the number of queries.

Each of the next $n$ lines contains a nonempty string $s_i$ ($1 \le s_i \le 10^5$) consisting of lowercase English letters.

Each of the next $m$ lines contains two integers $i$ and $j$ ($1 \le i, j \le n$) denoting a query.

It is guaranteed that in one test case the sum of all $|s|$ does not exceed $5 \times 10^5$, and that in all cases the sum of all $|s|$ does not exceed $5 \times 10^6$.

It is guaranteed that neither the sum of all $n$ nor the sum of all $m$ exceeds $10^6$.

For each query, output an integer denoting the answer.