A spiritual baba in Banani claims that, given two strings he can check if one string is available in another string as sub-sequence and not only that, he can even tell the minimum sub-array in which that sub-sequence exists. Now your friend wants to know if that spiritual baba is fraud or not. So, he wants you to make an application for him.

You are given two strings A & B. Now, find the minimum length sub-array of string ’A’ which contains the sub-sequence (string ‘B’). If such sub-sequence cannot be found, print -1.

Subsequence: suppose a string “abcdef” is given. Here, ”abcdef”, “abf”, “def”, “bce”, “a” are some example of sub-sequence of this string. But strings like “fea” and “dc” are not.

Input

The first line of the input contains an integer T (1 <= T <= 100) number of test cases. For each test case, two strings A (1 <= N <= 2500) and B (1 <= M <= 80) are given, each containing small letter English alphabet. Here N is length of string A and M is length of string B. Cases are separated by blank lines in input file.

Output

Output the case number and the expected answer for each test case.

Example

Input:
2
aabbaaccanbbbncc
abc

objectorientedprogramming
ii

Output:
Case 1: 6
Case 2: 15