小苯的ovo(A组、B组、C组)
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在网上聊天时，小苯非常喜欢发 "\rm ovo" 的颜文字表情，以表惊讶。
现在小苯有一个长度为 n 的字符串 S，他至多可以对 S 进行 k 次修改操作，具体的：
\bullet 选择下标 i\ (1 \leq i \leq n)，如果 S_i= \rm o，则修改为 \rm v；否则修改为 \rm o。

小苯希望在操作后，能从 S 中选择尽可能多的 "\rm ovo" 不相交的子串，他想知道最多可以选多少个，请你帮他算一算吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 100 \right) 代表数据组数，每组测试数据描述如下：
第一行两个正整数 n, k\ (1 \leq n \leq 5000, 0 \leq k \leq n)，分别表示 S 的长度和至多操作的次数。
第二行一个长度为 n 的字符串 S，保证 S 只由 \rm o 和 \rm v 两种字符构成。
（保证所有测试数据中，n 的总和不超过 5000。）

输出描述:

对于每组测试数据，在单独的一行输出一个整数，表示在操作后 \rm ovo 不相交子串的最大可能值。
示例1

输入

复制 
3
6 2
oooooo
5 0
ovovo
6 1
oooooo

输出

复制 
2
1
1

备注: