# Just Another String Matching Problem

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

## Description

Given a text string T and a pattern P, your task is to count the number of nonempty substrings of T that matches P.
Note that we're counting occurrences, so text 'aa' have two substrings that matches 'a', even though they're the same.
Formally, a text T is a non-empty string of lowercase letters, a pattern P is a non-empty string of lowercase letters, question marks (?) and asterisks (*). A question mark matches exact one letter, an asterisk matches zero or more letters.

## Input

The first line contains a single integer T (T <= 50), the number of test cases.
Each case contains exactly two non-empty lines. The first line is the text, T, the second line is the pattern P. T will only contain lowercase letters while P will only contain
lowercase letters, question marks and asterisks. Neither of them can have more than 3000 characters.

## Output

For each test case, print the case number and the number of substrings of T that matches P.

## Sample Input

3
aa
a
abb
?b
aab
*b*

## Sample Output

Case 1: 2
Case 2: 2
Case 3: 3

wujianhua

## Source

2009 Asia Regional Ningbo Online