如果一个字符串 $w$ 在字典序上严格小于它的所有循环移位，则称 $w$ 为 Lyndon 词。 字符串 $s$ 的最长 Lyndon 子串是指 $s$ 中作为 Lyndon 词的最长子串。 Chiaki 有 $n$ 个字符串 $s_1, s_2, \dots, s_n$。她有一些询问：对于给定的数对 $(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$。

输出格式

对于每个询问，输出一个整数表示答案。

样例

输入 1

1
2 1
aa
bb
1 2

输出 1

4