题目描述

Kostya 有一段由 $n$ 个单词组成的文本 $s$，这些单词均由拉丁字母组成。他还有两条纸带需要写下这段文本。第一条纸带最多可以容纳 $m$ 个字符，第二条纸带可以容纳任意数量的字符。

Kostya 需要选择一个数字 $x$，将前 $x$ 个单词写在第一条纸带上，其余的单词写在第二条纸带上。为了节省空间，单词之间不留空格，但每个单词必须完整地写在同一条纸带上。

由于第二条纸带上的空间非常宝贵，Kostya 希望你帮他选择最大的 $x$，使得 $s_1, s_2, \dots, s_x$ 这 $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$。

说明/提示

由 ChatGPT 4.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
2
2
1
0