Problem 1098. -- 调皮的复印机

1098: 调皮的复印机

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 122  Solved: 8
[Submit][Status][Web Board]

Description

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

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

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

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

Input

题目包含多组数据。

输入的第一行有一个整数T (1T110) 代表有T组数据。

对于每组数据分为两行:

第一行一个字符串S,如题目叙述;

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

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

Output

对于每组数据,输出的第一行为Case #x: ,其中x是数据编号(从1开始),

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

Sample Input

2
b
ab
aaa
bab

Sample Output

Case #1:
1
Case #2:
-1

HINT

Source

[Submit][Status]