Lyndon 부분 문자열

문자열 $w$가 자신의 모든 순환 회전(cyclic rotation)보다 사전 순으로 작으면 $w$를 Lyndon 단어라고 한다.

문자열 $s$의 가장 긴 Lyndon 부분 문자열은 $s$의 부분 문자열 중 Lyndon 단어이면서 가장 긴 것이다.

Chiaki에게는 $n$개의 문자열 $s_1, s_2, \dots, s_n$이 있다. Chiaki는 질의도 여러 개 가지고 있다. 각 질의는 쌍 $(i, j)$가 주어질 때 문자열 $s_i s_j$의 가장 긴 Lyndon 부분 문자열의 길이를 구하는 것이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 두 정수 $n$과 $m$ ($1 \le n, m \le 10^5$)이 주어진다. 각각 문자열의 개수와 질의의 개수이다.

이어지는 $n$개의 줄에는 소문자 영어 알파벳으로 이루어진 비어 있지 않은 문자열 $s_i$ ($1 \le s_i \le 10^5$)가 한 줄에 하나씩 주어진다.

이어지는 $m$개의 줄에는 질의를 나타내는 두 정수 $i$와 $j$ ($1 \le i, j \le n$)가 주어진다.

한 테스트 케이스에서 모든 $|s|$의 합은 $5 \times 10^5$을 넘지 않는다. 또한 모든 테스트 케이스에서 모든 $|s|$의 합은 $5 \times 10^6$을 넘지 않는다.

모든 $n$의 합과 모든 $m$의 합은 각각 $10^6$을 넘지 않는다.

각 질의에 대해 답을 나타내는 정수를 한 줄에 하나씩 출력한다.