BaoBao 被困在一个由 $n$ 个格子排成一行的迷宫中！格子从左到右编号为 $1$ 到 $n$，第 $i$ 个格子标记有一个字符 $s_i$，其中 $s_i$ 为 'L' 或 'R'。

从第 $m$ 个格子开始，BaoBao 将重复执行以下步骤，直到他逃出迷宫：

• 如果 BaoBao 位于第 $1$ 个格子或第 $n$ 个格子，则认为 BaoBao 到达了出口，从而成功逃脱。
• 否则，设 BaoBao 位于第 $t$ 个格子。如果 $s_t = \text{'L'}$，BaoBao 将移动到第 $(t - 1)$ 个格子；如果 $s_t = \text{'R'}$，BaoBao 将移动到第 $(t + 1)$ 个格子。

在执行上述步骤之前，BaoBao 可以更改某些格子中的字符以帮助自己逃脱。具体来说，对于第 $i$ 个格子，BaoBao 可以将 $s_i$ 从 'L' 改为 'R'，或者从 'R' 改为 'L'。

但更改格子中的字符是一项费力的工作。你的任务是帮助 BaoBao 计算他为了逃出迷宫必须更改的最少格子数量。

输入格式

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

第一行包含两个整数 $n$ 和 $m$ ($3 \le n \le 10^5$, $1 < m < n$)，分别表示迷宫中的格子数量和起始格子的索引。

第二行包含一个长度为 $n$ 的字符串 $s$，由字符 'L' 和 'R' 组成。$s$ 的第 $i$ 个字符表示第 $i$ 个格子中的字符。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示 BaoBao 为了逃出迷宫必须更改的最少格子数量。

样例

输入 1

3
3 2
LRL
10 4
RRRRRRRLLR
7 4
RLLRLLR

输出 1

0
2
1

说明

对于第一个样例测试用例，BaoBao 不需要更改任何字符即可从第 $3$ 个格子逃脱。因此答案为 $0$。

对于第二个样例测试用例，BaoBao 可以将 $s_8$ 改为 'R'，将 $s_9$ 改为 'R'，从而从第 $10$ 个格子逃脱。因此答案为 $2$。

对于第三个样例测试用例，BaoBao 可以将 $s_4$ 改为 'L'，从而从第 $1$ 个格子逃脱。因此答案为 $1$。