Ashish 忘记了他的密码。他记得他是用以下算法创建密码的：Ashish 从一段文本中选取最多 $k$ 个连续的单词，并取每个单词的首字母。然后，他可能将其中一些字母替换成了它们的“火星文”（l33tspeak）等价形式。具体来说，他可能将 "o" 替换为 "0"，"i" 替换为 "1"，"e" 替换为 "3"，"a" 替换为 "4"，"s" 替换为 "5"，"t" 替换为 "7"，"b" 替换为 "8"，和/或将 "g" 替换为 "9"。

例如，如果 Ashish 从《指环王：护戒使者》的第一句话——“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”——中选取密码，他会将其简化为 "tbilcwhafiparmdmotcaaloth"。那么密码可能是 "tbilcwh"、"7b1lcwh4f"、"a"、"4" 或 "4al07h" 等。

Ashish 的浏览器安装了一个特殊扩展程序，可以阻止计算机上传任何包含他密码的字符串。为了找出他从哪段文本中选取了密码，Ashish 创建了一个网页来利用这个扩展程序。每秒钟，网页都会告诉浏览器发布一个针对新文本段落的“密码字符串”：该字符串包含了 Ashish 可能从该段文本中选择的所有可能的密码。一旦浏览器无法发布这样的字符串，Ashish 就会知道他从哪里选取了密码。

例如，如果 $k = 2$ 且文本段落包含以字母 "google" 开头的单词，那么该段落的一个密码字符串是 "goo0og00gle9o909l3"。原字符串中所有长度 $\le 2$ 的子串，以及它们所有的火星文等价形式，都包含在这个新字符串中。

给定一段文本中单词的首字母，该段落的“密码字符串”的最少字符数是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含两行。第一行包含整数 $k$。第二行包含一个字符串 $S$，表示文本段落中单词的首字母。$S$ 仅包含字符 'a' - 'z'，且没有空格。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是 $S$ 的密码字符串的最少字符数。

数据范围

$1 \le T \le 20$。 $S$ 将至少包含 $2 \times k$ 个字符。 存在一个字符数最多为 $10^{18}$ 的密码字符串。

子任务 1

$S$ 最多包含 1000 个字符。 $k = 2$。

子任务 2

$S$ 最多包含 5000 个字符。 $2 \le k \le 500$。

样例

样例输入 1

4
2
poppop
2
google
2
tbilcwhafiparmdmotcaaloth
10
tbilcwhafiparmdmotcaaloth

样例输出 1

Case #1: 6
Case #2: 18
Case #3: 53
Case #4: 1136

说明

在第一个样例输入中，一个可能的密码字符串是 "0ppop0"。

在第二个样例输入中，一个可能的密码字符串是 "goo0og00gle9o909l3"。