Comet OJ

C1758 [CCPC2017秦皇岛站-L] One­Dimensional Maze

内存限制：64 MB 时间限制：1000 ms

题目描述

BaoBao is trapped in a one­dimensional maze consisting of $n$ grids arranged in a row! The grids are numbered from 1 to $n$ from left to right, and the $i$-­th grid is marked with a character $s_i$, where $s_i$ is either 'L' or 'R'.

Starting from the $m$-­th grid, BaoBao will repeatedly take the following steps until he escapes the maze:

  • If BaoBao is in the 1st grid or the $n$-­th grid, then BaoBao is considered to arrive at the exit and thus can escape successfully.
  • Otherwise, let BaoBao be in the $t$-­th grid. If $s_t=$ 'L', BaoBao will move to the $(t-1)$-th grid; If $s_t=$ 'R' , Baobao will move to the $t+1$-­th grid.

Before taking the above steps, BaoBao can change the characters in some grids to help himself escape. Concretely speaking, for the $i$-­th grid, BaoBao can change $s_i$ from 'L' to 'R', or from 'R' to 'L'.

But changing characters in grids is a tiring job. Your task is to help BaoBao calculate the minimum number of grids he has to change to escape the maze.

输入格式

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

The first line contains two integers $n$ and $m(3 \le n \le 10^5, 1<m <n)$, indicating the number of grids in the maze, and the index of the starting grid.

The second line contains a string $s(|s|=n)$ consisting of characters 'L' and 'R'. The $i$-­th character of $s$ indicates the character in the ­$i$-th grid.

It is guaranteed that the sum of $n$ over all test cases will not exceed $10^6$.

输出

For each test case output one line containing one integer, indicating the minimum number of grids BaoBao has to change to escape the maze.

样例

样例输入 1

3
3 2
LRL
10 4
RRRRRRRLLR
7 4
RLLRLLR

样例输出 1

0
2
1

提示