A. Переносы строк
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кости есть текст $$$s$$$ из $$$n$$$ слов, состоящих из букв латинского алфавита. Также у него есть две полоски, на которые он должен выписать текст. На первую полоску помещается $$$m$$$ символов, а на вторую — сколько угодно.

Костя должен выбрать число $$$x$$$ и выписывает первые $$$x$$$ слов из $$$s$$$ на первую полоску, а все остальные — на вторую. Ради экономии места слова выписываются без отступов, но каждое слово должно полностью быть на одной полоске.

Так как место на второй полоске очень ценно, Костя просит вас выбрать максимальное возможное число $$$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$$$.

Пример
Входные данные
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