题目描述

新格尔软件公司有一台调皮的复印机，他在复印文件的时候，总会默默地对一些字符做一些操作。最近他对于包含字母 a 和字母 b 的字符串很感兴趣。

如果文件中有一个字符串 ab，那么经过一次复印以后，他会变成 aaab。

也就是说，如果遇到了字母 a 他会输出 aa，如果有字母 b 他会输出 ab。

现在呢，实习生菜喜武手里有一份文件，就是一个字符串 $S$，以及一份可能经过了复印的文件的一小段，就是字符串 $T$，他想知道他手里的这一小段最少可能被复印过几次，如果这一小段并不属于这个文件，那么输出 $-1$。

输入格式

题目包含多组数据。

输入的第一行有一个整数 $T$ $(1 \leq T \leq 110)$ 代表有 $T$ 组数据。

对于每组数据分为两行：

第一行一个字符串 $S$，如题目叙述；

第二行一个字符串 $T$，如题目叙述。

两个串 $S$, $T$ 长度均小于 $10000$。

输出格式

对于每组数据，输出的第一行为 Case #x:，其中 $x$ 是数据编号（从 $1$ 开始），

第二行一个整数，题中描述的答案。

样例输入

2
b
ab
aaa
bab

样例输出

Case #1:
1
Case #2:
-1