1255KMP

//In the Name of Allah Most Gracious, Most Merciful//
/*If you want something you've never had, you have  to do something you never did.*/

#include<bits/stdc++.h>
using namespace std;


#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define M 1000007
#define INF 1e9
#define INFL 1e18
#define PI acos(-1)
#define mp make_pair
#define MAX 100000
//const int fx[]= {+1,-1,+0,+0};
//const int fy[]= {+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
int failure[1000010];



void build_failure_function(string pattern,int m)
{
    failure[0]=0;
    failure[1]=0;
    for(int i=2;i<=m;i++)
    {
        //i is the length of the prefix we are dealing with
        //j is the index of the largest next partial match
        //(the largest suffix/prefix) of the string under index i-1
        int j=failure[i-1];
        while(true)
        {

        if(pattern[j]==pattern[i-1])
        {
            // check the last character of prefix of length i expands the current candidate
            failure[i]=j+1;
            break;
        }
        if(j==0)
        {
            //if we cannot expand even the empty string
            failure[i]=0;
            break;
        }
        //else go to the next best candidate partial match
        j=failure[j];

        }
    }
}


int kmp(string text,string pattern)
{
    int n=text.size();
    int m=pattern.size();
    build_failure_function(pattern,m);
    int cnt=0;
    int i=0;//the initial state of automation is the empty string
    int j=0; //the first character of the text
    int spos=0;
    while(true)
    {
        if(j==n)
        {
            return cnt;
        }
        if(text[j]==pattern[i])
        {
            i++;
            j++;
        if(i==m)
        {
//            return true;
            j=j-m+1;
            i=0;
            cnt++;
//            break;
        }

        }
        else
        {
            if(i==0)
            {
                //if we reached the empty string and failed to expand
                //even it ;we go to the
                //next character from the text,the state of automation
                //remains zero
                j++;
            }
            else
            {
                i=failure[i];
            }
        }
    }
    return cnt;
}

int main()
{

   //  #ifndef ONLINE_JUDGE
   //    freopen("input.txt","r",stdin);
    //   freopen("1255.txt","w",stdout);
  //   #endif
    int t;
    int kase=0;
    scanf("%d ",&t);
    while(t--)
    {

    string a,b;
    char aa[1000010];
    char bb[1000010];
    scanf("%s",aa);
    scanf("%s",bb);
    a=aa;
    b=bb;
//    cout<<a<<" "<<b<<endl;
    int ans=kmp(a,b);
    printf("Case %d: %d\n",kase+1,ans);
    kase++;
//    memset(failure,0,sizeof failure);
    }
    return 0;
///Before submit=>
///    *check for integer overflow,array bounds
///    *check for n=1
}