Kostya 的文本 $$$s$$$ 由拉丁字母组成的 $$$n$$$ 个单词组成。他还有两条纸条,他必须在上面写下文字。第一个条带可以容纳 $$$m$$$ 个字符,而第二个条带可以容纳所需数量的字符。
Kostya 必须选择一个数字 $$$x$$$ 并将 $$$s$$$ 中的前 $$$x$$$ 个单词写在第一个条上,而所有剩余的单词则写在第二个条上。为了节省空间,字写得没有间隙,但每个字必须完全在一条纸上。
由于第二条上的空间非常宝贵,Kostya 要求您选择最大可能的数字 $$$x$$$,以便所有单词 $$$s_1, s_2, \dots, s_x$$$ 适合长度为 $$$m$$$ 的第一个条。
输入
第一行包含一个整数 $$$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$$$,使得前 $$$x$$$ 单词的总长度不超过 $$$m$$$。
示例
输入 #1
5 3 1 a b c 2 9 alpha beta 4 12 hello world and codeforces 3 2 ab c d 3 2 abc ab a
输出 #1
1 2 2 1 0