디스플레이

ACM(Advanced Communication Machinery)은 잘 알려진 휴대폰 제조사입니다. 요즘 이 회사의 프로그래머들은 새 휴대폰 ACM Touch의 GUI를 만들고 있고, 디자이너들은 여기에 스크롤바를 넣고 싶어 합니다.

스크롤바는 화면, 창, 뷰포트에 다 들어가지 않는 연속된 내용(텍스트, 그림, 또는 동영상의 재생 시간 등 무엇이든)을 스크롤해서 볼 수 있게 해 주는 GUI 컨트롤입니다. 보통 보기 영역의 한쪽이나 양쪽에 놓인 긴 직사각형 띠로 그려지며, 그 안에는 트랙을 따라 끌어서 문서를 움직이는 막대(썸)가 들어 있습니다. 이 썸의 크기를 계산하려면 문서 전체를 화면에 표시했을 때 몇 줄을 차지하는지 알아야 합니다.

ACM Touch에서 텍스트는 다음 규칙으로 배치됩니다.

1. 표시 방향은 왼쪽에서 오른쪽으로, 그리고 위에서 아래로 진행합니다.
2. 단어는 하나의 공백 또는 줄바꿈으로 구분합니다.
3. 단어 안에는 공백이 들어가지 않습니다.
4. 현재 단어가 현재 줄의 남은 공간에 들어가지 못할 때에만 줄을 바꿉니다.
5. 새 줄의 맨 앞에 공백이 오게 되면 그 공백은 표시하지 않습니다.

주어진 텍스트를 표시하는 데 필요한 최소 줄 수를 구하는 프로그램을 작성하세요. 모든 단어의 길이는 열 너비 이하라고 가정해도 됩니다.

예를 들어 "ACM is short for Association for Computing Machinery"는 아래 그림과 같이 배치할 수 있습니다. 첫 번째 배치는 ACM Touch에 적합하지만, 두 번째는 그렇지 않습니다.

첫 번째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어집니다.

각 테스트 케이스는 두 줄로 이루어집니다. 첫 번째 줄에는 휴대폰 화면의 너비(열 개수) $w$ ($1 \le w \le 100$)가 주어집니다. 두 번째 줄에는 표시할 텍스트가 주어지며, 길이는 최대 2000자입니다. 텍스트는 공백 하나로 구분된 로마자 알파벳 단어들로 이루어지며, 길이가 $w$보다 긴 단어는 없습니다.

각 테스트 케이스마다 위 규칙에 따라 텍스트를 표시하는 데 필요한 최소 줄 수를 정수 하나로 출력합니다.