Lost Password (Large)

Ashish has forgotten his password. He still remembers how he built it. He took up to k consecutive words from a passage of text, kept the first letter of each word in order, and then may have replaced some of the letters with their l33tspeak forms. There are eight allowed replacements: o to 0, i to 1, e to 3, a to 4, s to 5, t to 7, b to 8, and g to 9.

Let S be the string of the first letters of the words in a passage, in order. A password is a string obtained by taking one substring of S whose length is between 1 and k, then keeping or replacing each of its letters under the rule above.

For example, if Ashish took his password from 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", then S is "tbilcwhafiparmdmotcaaloth", and the password might be "tbilcwh", "7b1lcwh4f", "a", "4", or "4al07h".

Ashish has a browser extension that blocks the upload of any string containing his password as a substring. To find out which passage his password came from, Ashish built a webpage. Once every second the page makes the browser post the "password string" of one passage: a string that contains, as a substring, every password Ashish could have chosen from that passage. The first time a post fails, Ashish knows where he took his password from.

For example, if k = 2 and the words of a passage start with the letters "google", then "goo0og00gle9o909l3" is a password string for that passage. Every substring of length at most 2 of the original string, and every l33tspeak form of those substrings, appears inside it.

Given S, find the minimum number of characters in a password string for that passage.

The first line contains the number of test cases, T. T test cases follow. Each test case consists of two lines. The first line contains the integer k. The second line contains the string S, the first letters of the words in a passage. S contains only the characters 'a' to 'z', with no spaces.

Limits

• $1 \le T \le 20$
• The length of S is at least $2k$ and at most 5000.
• $2 \le k \le 500$
• A password string of length at most $10^{18}$ always exists.

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

For k = 2 and S = "poppop", "0ppop0" is a password string.

For k = 2 and S = "google", "goo0og00gle9o909l3" is a password string.