Display

ACM (Advanced Communication Machinery) is a well-known mobile-phone manufacturer. These days its programmers are building the GUI for a brand-new phone, ACM Touch, and the designers want a scrollbar on it.

A scrollbar is a GUI control that lets you scroll through continuous content (text, images, or anything else, including time in video applications) so you can view content that does not fit inside the display, window, or viewport. It is usually a long rectangular strip along one or two sides of the viewing area, holding a bar (the thumb) that you drag along a track to move the document. To size the thumb, we need to know how many rows the whole document takes up when it is displayed.

On ACM Touch, text is laid out like this:

1. The display fills from left to right, and from the top downward.
2. Words are separated by either a single blank space or a newline.
3. A word never contains a blank space.
4. A newline is inserted if and only if the current word does not fit in the remaining space of the current row.
5. If a blank space would land at the beginning of a new row, it is not displayed.

Write a program that computes the minimum number of rows needed to display a given text. You may assume that every word is no longer than the column width.

For example, "ACM is short for Association for Computing Machinery" can be laid out as shown below. The first layout is valid for ACM Touch; the second is not.

The first line contains an integer $T$ ($1 \le T \le 20$), the number of test cases.

Each test case consists of two lines. The first line is an integer $w$ ($1 \le w \le 100$), the width of the phone screen in columns. The second line is the text to display; its length is at most 2000 characters, it consists of Roman letters separated by single blank spaces, and no word is longer than $w$.

For each test case, print a single integer: the minimum number of rows needed to display the text according to the rules above.