Again our country is being attacked by the Enemy country. The soldiers are coming in a line. There are different kinds of soldiers. Now they have Big Dragons. But again our spy informed us how Big Dragons look like. Now you have to find how many Big Dragons they can have so that we can prepare ourselves.

আবারো আমাদের দেশকে শত্রু দেশ আক্রমন করতে আসতেছে। শত্রুসেনারা এক লাইন ধরে আসতেছে।তাদের মধ্যে বিভিন্ন ধরনের সেনা আছে। আমাদের স্পাই খবর দিছে যে তাদের সাথে এবার বড় ড্রাগন আছে। সে বড় ড্রাগনের একটা ছবিও একে পাঠাইছে। এখন তোমাকে তাদের মধ্যে কতগুলা বড় ড্রাগন থাকতে পারে এইটা বের করতে হবে।

Input

The first line of input file contains the number of test cases T (T ≤25). Each test case is composed of two lines. The first line describes the line of soldiers using a string (a sequence of nonempty alphabetical character). Now a Big Dragon can contain more than one character (that’s why it is big). There will be no space between two consecutive characters. The second line contains another string describing a Big Dragon. Now you have to find the maximum possible number of Big Dragons in the line of soldiers, that is, number of all occurrence of the 2^nd string in the previous string. The maximum number of characters will not be greater than 100. The problem is case sensitive. Two Big Dragons may overlap.

ইনপুট ফাইলের প্রথম লাইনে থাকবে কতগুলা টেস্ট কেস আছে, একটা নাম্বার T(T≤25) দিয়ে। প্রত্যেকটা টেস্ট কেস এ 2 টা লাইন থাকবে। প্রথম লাইনে থাকবে সেনাদের বর্ননা, একটা স্ট্রিং(একটা ননএম্পটি আলফাবেটিকাল ক্যরেক্টারের সিকুয়েন্স)। দ্বিতীয় লাইনে থাকবে বড় ড্রাগনের বর্ননা। এখন একটা বড় ড্রাগন একাধিক ক্যরেক্টারের হতে পারে(তাই এইটা বড় ড্রাগন)। এখন তোমাকে সেনাদের লাইনে কতগুলা বড় ড্রাগন আছে এইটা বের করতে হবে, তার মানে আগের স্ট্রিং-এ পরের স্ট্রিংটা কতবার আছে এইটা বের করতে হবে। সেনার সংখা 100 এর বেশি হবে না। প্রব্লেমটা কেস সেন্সেটিভ। দুইটা ড্রাগন ওভারল্যাপ করতে পারে।

Output

For each case, print a line like “Case X: N”, without the quotes, where X is the number of test case starting from 1 and N is the number of Big Dragons. Check sample input and output sections for more details.

প্রত্যেকটা কেস এর জন্য একটা লাইন “Case X: N” প্রিন্ট করতে হবে, কোট ছাড়া, যেখানে X হল 1 থেকে শুরু হওয়া টেস্ট কেস এর নাম্বার, আর N হল বড় ড্রাগন এর সংখা। বিস্তারিত এর জন্য স্যাম্পল ইনপুট এবং আওটপুট দেখ।

Example

Input:
5
ssddDddssddDSdsdsd
ddD
adnalkdjfkasdjkaa
a
aaknklopmnhlakdjsfksdakldjfalkdfla
la
AAAAAA
AA
AbAbAbAb
bAb

Output:
Case 1: 2
Case 2: 5
Case 3: 2
Case 4: 5
Case 5: 3

For case 5: we start matching from the beginning. At first 'bAb' matched with 'AbAbAbAb'. Next match will be 'AbAbAbAb'. Third match is ''AbAbAbAb'