你需要实现一个可以说是最重要的算法：二分查找。更准确地说，你有一个已排序的对象数组，以及一个想要插入到数组中的新对象。为了找到插入位置，你可以将你的对象与数组中的对象进行比较。每次比较的结果要么是“大于”（意味着你的对象应该插入到被比较对象的右侧），要么是“小于”（意味着你的对象应该插入到被比较对象的左侧）。为简化起见，本题中比较结果永远不会是“等于”。题目保证，当你的对象大于数组中的某个对象时，它也大于该对象左侧的所有对象；同样，当你的对象小于数组中的某个对象时，它也小于该对象右侧的所有对象。如果数组有 $n$ 个元素，那么你的算法共有 $n+1$ 种可能的输出结果。

在本题中，并非所有的比较代价都相同。具体来说，将你的对象与数组中第 $i$ 个对象进行比较的代价为 $a_i$，这是一个介于 1 到 9 之间的整数。

在最坏情况下，你的二分查找的总代价是多少？假设你采取最优策略，并试图最小化最坏情况下的总代价。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每一行包含一个数字序列，描述了一个测试用例中各比较的代价 $a_i$。数组的大小 $n$ 由该序列的长度给出。

输出格式

对于每个测试用例，输出一行 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最坏情况下的二分查找总代价。

数据范围

$1 \le T \le 50$。 所有数字均在 1 到 9 之间（含 1 和 9）。 同一行内的数字之间没有空格。

小数据范围

$1 \le n \le 10^4$。

大数据范围

$1 \le n \le 10^6$。

样例

样例输入 1

4
111
1111
1111111
1111119

样例输出 1

Case #1: 2
Case #2: 3
Case #3: 3
Case #4: 10