提示: 欢迎访问OurACM平台。
Problem 1937 Palindrome

Accept: 96    Submit: 139
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

A palindrome is a string that is the same whether it is read from left to right or from right to left. Little Dazdraperma likes palindromes a lot. As a birthday gift she received two strings A and B. Now she is curious if there is a way to insert string B into string A so that the resulting string is a palindrome. You agreed to help her and even tell how many different variants of such insertions exist. Two variants are considered different if string B is inserted in different places. Return the number of possible insertion variants.

For example, let A="aba" and B="b". You can insert B in 4 different places: * Before the first letter of A. The result is "baba" and it is not a palindrome. * After the first letter 'a'. The result is "abba" and it is a palindrome. * After the letter 'b'. The result is "abba" and it is also a palindrome. * After the second letter 'a'. The result is "abab" and it is not a palindrome. So, the answer for this example is 2.

Input

Input contains multiple cases.

The first line contains an integer T representing the number of cases.

Then following T cases.

For each test case, contains two lines,first line is A,second line is B.

A and B will each contain between 1 and 50 characters, inclusive.

Each character of A and B will be a lowercase letter ('a'-'z').

Output

For each test case, print a line containing the test case number (beginning with 1) and different variants of such insertions.

Sample Input

1 aba b

Sample Output

Case 1: 2

Source

FZU2010暑期集训队选拔赛I

Submit  Back  Status  Discuss