题目描述

你发现你的一个朋友已经开始玩最走的Master谱面了，这时你打算做点坏事。

你找出了朋友的一个长度为n的音阶打击序列，为了简化模型，这个序列只有o（命中）和x（不命中）。

下面定义音阶打击序列每个位置的当前连击数：

• 有一个累加器，初始值设为0。
• 将序列从左到右依次扫描，对于当前某个字符，若它是o，那么累加器加1，否则累加器重置为0。
• 序列每个位置的当前连击数，等于扫描过这个位置后累加器的值。
• 例如，对于音阶打击序列oooxoo，每个位置的当前连击数依次是1,2,3,0,1,2。

整个音阶打击序列的分数，等于打击序列每个位置的当前连击数之和。例如，对于音阶打击序列oooxoo，分数等于1+2+3+0+1+2=9。

现在你有k次动手脚的机会，每次机会可以将这个打击序列的一个o修改为x，k次机会可以全部使用。部分使用或完全不使用。你想知道所有修改方案中，分数的最小值可以是多少。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 \( T \left( 1 \leq T \leq 10 \right) \) 代表数据组数，每组测试数据描述如下： 第一行，输入两个正整数 \( n \)，\( k \left( 1 \leq n \leq 20 \right) \)，\( 1 \leq k \leq n \) 代表序列的长度和机会的次数。 第二行，输入一个长度为n的字符串，保证出现的字符只全是o或x。 对于同一个测试点，保证所有数据的n之和不超过 \( 200 \)。

输出描述

对于每组数据，输出一行一个整数，表示所有修改方案中，分数的最小值可以是多少。

Samples

2
4 2
oxoo
6 1
oooxoo

1
5

Limitation

1s, 1024KiB for each test case.