题目描述

小明是一个打字员，现在有一篇文章有n个单词，现在他需要把这篇文章手动敲在电脑文档里面。现在有两个窗口，第一个窗口可以容纳m个单词。第二个窗口不限容量。

小明需要保证一个单词必须完整的在一个窗口内，同时为了节省空间，需要先把第一个窗口尽量填充完再使用第二个窗口。你需要求出，最多在第一个窗口输入多少单词数x

输入格式

第一行包含一个整数 $t$ ( $1 \le t \le 1000$ ) - 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ( $1 \le n \le 50$ ; $1 \le m \le 500$ )--列表中的字数和第一条上的最大字符数。

接下来的 $n$ 行包含一个由小写拉丁字母组成的单词 $s_i$ ，其中 $s_i$ 的长度不超过 $10$ 。

输出格式

一个整数x

输入样例

5
3 1
a
b
c
2 9
alpha
beta
4 12
hello
world
and
genshinimpact
3 2
ab
c
d
3 2
abc
ab
a

输出样例

1
2
2
1
0