题目描述

Cjwssb得到了你的帮助，显得很开心，跟你道谢，你回谢了他。但随后他由于少听了一些词，对你的回谢造成了误会，这使你们两个产生了隔阂，你很不甘心，于是打算告诉他这句话有几种理解方式，以告诉他他误解你了。一句话的理解方式如下

对于一句原句和听到的句子，理解方式是将听到的句子替换掉原句的相同部分，替换成*，使得原句形成一个新的句子，以达到新的意思，你的任务是统计有多少种意思

输入格式

第一行一个整数T，表示T组测试点

每组测试点两个字符串，一个字符串一行，第一行字符串是原句，第二行是听到的句子

输出格式

对于每一个测试点，输出一行“Case #x: y”,x表示测试点，y表示答案，由于答案可能很大，你只需要输出答案%1000000007.

4
hehehe
hehe
woquxizaolehehe
woquxizaole
hehehehe
hehe
owoadiuhzgneninougur
iehiehieh

Case #1: 3
Case #2: 2
Case #3: 5
Case #4: 1

提示

在第一个测试点，“ hehehe”有三个理解意思，分别是“*he”, “he*”, “hehehe”.

在第三个测试点，“hehehehe”有五个理解意思，分别是“*hehe”, “he*he”, “hehe*”, “**”, “hehehehe”.

对于100%的数据

T <= 30

|A| <= 100000

|B| <= |A|

By：2016 Mul