Lost Password | cho.sh

Problem

Ashish forgot his password. He still remembers how he built it. He took up to $k$ consecutive words from a passage of text and kept the first letter of each word. Then he may have replaced some of those letters with their l33tspeak digits:

letter	digit
o	0
i	1
e	3
a	4
s	5
t	7
b	8
g	9

Each letter is replaced on its own, so the set of replaced letters can be any subset.

Take the first sentence of The Fellowship of the Ring, "This book is largely concerned with Hobbits, and from its pages a reader may discover much of their character and a little of their history". The first letters of its words spell tbilcwhafiparmdmotcaaloth. If $k$ had been 9 or more, the password could be tbilcwh, 7b1lcwh4f, a, 4, or 4al07h.

A browser extension stops Ashish's computer from uploading any string that contains his password. To find the passage he used, Ashish wrote a webpage that tells the browser, once every second, to post a password string for a new passage: a string that contains every password Ashish could have taken from that passage as a contiguous substring. The moment his browser fails to post one, Ashish knows which passage the password came from.

For example, with $k = 2$ and a passage whose word initials spell google, one password string is goo0og00gle9o909l3. It contains every substring of google of length 1 or 2 together with every l33tspeak form of those substrings.

Given the first letters of the words in a passage, find the smallest possible number of characters in a password string for that passage.

Input

The first line has the number of test cases $T$ . Each test case takes two lines. The first line has the integer $k$ . The second line has the string $S$ , the first letters of the words in a passage, written with no spaces.

Limits:

$1 \le T \le 20$
$k = 2$
$2k \le |S| \le 1000$
$S$ contains only the characters a to z

Output

For each test case, print one line of the form "Case #x: y", where x is the test case number starting from 1 and y is the smallest number of characters in a password string for $S$ .

Note

For $k = 2$ and $S =$ poppop, one shortest password string is 0ppop0. For $k = 2$ and $S =$ google, one shortest password string is goo0og00gle9o909l3.