题目描述

小$\tt Z$ 是一名太空探险家，驾驶一艘宇宙飞船在一条坐标轴上航行。飞船的自动驾驶系统存储了一个长度为 $n$ 的导航指令序列，由字符 L 和 R 组成：

• L 表示向左移动一个单位（即从当前位置 $p$ 移动到 $p-1$）；
• R 表示向右移动一个单位（即从当前位置 $p$ 移动到 $p+1$）。

现在，小$\tt Z$ 观察到，执行完所有的指令之后，飞船总共经过了原点 $0$ 共 $m$ 次。

同时已知初始位置 $x$ 的范围为 $[-10^{6}, 0)∪(0,10^6]$，小$\tt Z$ 想知道，飞船的初始位置 $x$ 有多少种可能（即在 $-10^6\sim10^6$ 之间且不为 $0$ 的可能数）。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$。

每个测试用例的第二行包含一个由 $n$ 个字符 L 和 R 组成的字符串 $s$，表示导航指令序列。

输出格式

对于每个测试用例，输出所有满足要求可能的初始位置的方案数。

输入输出样例

2
3 2
RLR
2 0
RR

1
1999998

样例 $\tt \#1$说明

初始位置在 -1 时，RLR 可经过原点 $2$ 次；

初始位置只要不是 $-2,-1$ 即可

数据范围

$50\%:\sum_{t=1}^{T}|S|\le10^3$

$100\%:\sum_{t=1}^{T}|S|\le10^6,1\le t\le 10^2,m$ 为非负数

$|S|$表示字符串 $S$ 的长度