净
题号：NC232740
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述


如果你厌倦了长文题意，可以参考下面的伪代码理解题意。

你有一个数组 表示结点 i 的父亲结点编号，初始 ；另有一个数组 表示结点 i 的属性（左孩子结点还是右孩子结点）。初始 ，。

即初始的树如右图所示：

接下来给出一个操作序列 str，其中会包含三种字符 ：

  1. 操作：对所有上一轮新生成的结点中（初始新生成的结点是 2,3）所有 （左孩子）的结点，生成两个孩子结点，一个左孩子一个右孩子。

  1. 操作：对所有上一轮新生成的结点中（初始新生成的结点是 2,3）所有  （右孩子）的结点，生成两个孩子结点，一个左孩子一个右孩子。

  1. 操作：对所有上一轮新生成的结点中（初始新生成的结点是 2,3）所有的结点（不论属性），生成两个孩子结点，一个左孩子一个右孩子。

最终求执行完 k 次操作序列 str 后（可以理解成将序列 str 复制成原来的 k 倍并依次执行）树的直径长度（树上一条链包含最多的结点个数）是多少。

如果你厌倦了长文题意，可以参考下面的伪代码理解题意：



代码中  表示利用 数组求树的直径。

输入描述:

全文第一行输入一行一个正整数 ，表示数据组数。

接下来对每组数据，第一行输入两个正整数 ，分别表示 str 的长度和操作次数。

第二行输入这个长度为 n 的操作序列 str，由 n 个仅可能为 、、 的大写英文字母组成。

输出描述:

每组数据对应一行输出，表示答案。
示例1

输入

复制 
2
3 1
LLM
1 2
L

输出

复制 
6
5

说明

对于样例 #2，真正的操作序列实际上是将 str=\tt 'L' 执行 2 次，即 str'=\tt 'LL'。

样例 #1 和 #2 中，树的形态及答案的求解过程：

样例 #1 中取 3\leftrightarrow1\leftrightarrow2\leftrightarrow4\leftrightarrow6\leftrightarrow8 即可，样例 #2 中少了 8,9,10,11 四个结点，因此选择上文所述前五个结点构成的链即可。