lightoj1013

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

typedef int64_t ll;
char a[45],b[45];
string h,u;
int dx=0;
ll dp2[33][33];
ll dp[33][33][64];
int solve(int x,int y)
{
   // cout<<x<<' '<<y<<endl;
    if(x==h.size()&&y==u.size())return 0;
    if(x>h.size()||y>u.size())return 1e5;
         if(dp2[x][y]!=-1)return dp2[x][y];
    int ans=1e5;
    if(x<h.size()&&y<u.size()&&h[x]==u[y])
        ans=1+solve(x+1,y+1);
    ans=min(ans,min(1+solve(x,y+1),1+solve(x+1,y)));
    return dp2[x][y]=ans;
}
ll calc(int x,int y,int l)
{
    ll ans=0;

    if(x==h.size()&&y==u.size())return (int)l==dx;
    if(x>h.size()||y>u.size())return 0;
    if(dp[x][y][l]!=-1)return dp[x][y][l];
    if(x<h.size()&&y<u.size()&&h[x]==u[y])
        return dp[x][y][l]=calc(x+1,y+1,l+1);
    ans+=calc(x+1,y,l+1);
    ans+=calc(x,y+1,l+1);

    return dp[x][y][l]=ans;
}
int main()
{
    int t;
    cin>>t;
   // freopen("out.txt","w",stdout);
    int g=0;
    while(t--){
            g++;
            memset(dp,-1,sizeof dp);
            memset(dp2,-1,sizeof dp2);
    scanf("%s%s",a,b);
    h=a,u=b;
      dx=solve(0,0);
      printf("Case %d: %d %lld\n",g,dx,calc(0,0,0));

    }return 0;
}