Scrolling Sign

Electric scrolling signs are often used for advertising. A sign displays exactly $k$ characters. When the sign is switched on, every character position is empty (it shows a space). During each time step, all characters on the sign shift one position to the left, and one new character enters at the right-most position; the character that was in the left-most position leaves the sign.

For some sequences of words, characters can be reused from one word to help form the next. For example, on a sign with three character positions, the sign can display CAT, then ATE, then TED by scrolling in just the five characters CATED.

You are given a message: a list of words that must all be displayed, in the given order. The fewer letters are scrolled in, the more people can see the whole message. Between the words of the message the sign may pass through other words that are not part of the message, but every word of the message must appear in the given order. Find the smallest number of letters that must be scrolled into the sign to display the entire message.

The first line contains a single integer $n$: the number of test cases.

Each test case begins with a line containing two integers $k$ and $w$: the number of character positions on the sign and the number of words in the message, with $1 \le k, w \le 100$. The next $w$ lines each contain one word of the message, made of exactly $k$ uppercase letters.

For each test case, print one line with a single integer: the minimum number of letters that must be scrolled into the sign so that it displays every word of the message, in order.