长度为 $n$ 的字符串 $s$ 的后缀数组是一个从 $1$ 到 $n$ 的整数排列 $sa$，使得 $s[sa_1..n], s[sa_2..n], \dots, s[sa_n..n]$ 是 $s$ 的所有非空后缀按字典序排序后的列表。$s$ 的后缀排名表是一个从 $1$ 到 $n$ 的整数排列 $rank$，使得 $rank_{sa_i} = i$。

Kotori 有一个字符串 $s = s_1s_2 \dots s_n$。她想要进行 $m$ 次查询。在第 $i$ 次查询中，给定 $s$ 的一个子串 $x = s[l_i..r_i]$，Kotori 想知道后缀 $s[k_i..r_i]$ 在 $x$ 中的排名。

注意：$s[l..r]$ 表示 $s$ 中从第 $l$ 个位置开始到第 $r$ 个位置结束（包含两端）的子串。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 5 \times 10^4$)，分别表示字符串的长度和查询次数。

第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写英文字母组成。

接下来的 $m$ 行，每行包含三个整数 $l_i, r_i$ 和 $k_i$ ($1 \le l_i \le r_i \le n, l_i \le k_i \le r_i$)，表示一次查询。

保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $5 \times 10^4$。

输出格式

对于每次查询，输出一行，包含一个整数，表示答案。

样例

样例输入 1

2
10 4
baaabbabba
2 8 3
1 1 1
2 3 2
2 5 4
20 3
cccbccbadaacbbbcccab
14 17 16
3 20 17
17 20 18

样例输出 1

2
1
2
3
4
15
3