/*In the name of Almighty Allah*/

#include<bits/stdc++.h>

#define pb          push_back
#define mp          make_pair
#define Fill(a,b) memset (a, b, sizeof a)
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define mod         1000000007
#define For(i,a,b)  for(int i=a;i<b;i++)
#define rof(i,a,b)  for (int i=a;i>=b;i--)

using namespace std;

typedef long long       ll;
typedef double          dl;
typedef vector<int>     vi;

int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}

void dbga ( int a[], int s )
{
    For ( i, 0, s ) cout << a[i] << " ";
    cout << endl;
}

void dbgv ( vector < string > v )
{
    For ( i, 0, sz(v) ) cout << v[i] << " ";
    cout << endl;
}

void rev ( int a[], int s )
{
    for ( int i = 0,j = s-1; i < s/2; i++, j-- ) {
        swap ( a[i], a[j] );
    }
}


string to_s(int t)
{
  stringstream ss;
  ss << t;
  return ss.str();
}


struct edge {
    int w,s;
};

bool cmp ( const edge &a, const edge &b )
{
    return a.w < b.w;
}

ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

/*
bool isprime[100123];
vector < int > prime;

void seive ()
{
    int num = 100000, sqr = 340;
    for ( int i = 3; i <= num; i+=2 ) isprime[i] = 1;

    for ( int i = 3; i <= sqr; i+=2 ) {
        if ( isprime[i] ) {
            for ( int j = i * i; j <=num; j+=(i*2) ) {
                isprime[j] = 0;
            }
        }
    }

    prime.pb ( 2 );
    isprime[2] = 1;

    for ( int i = 3; i <=num; i+=2 ) {
        if ( isprime[i] ) prime.pb ( i );
    }
}
*/

string A, B, an, v;
int dp[123][123];
bool visited[123][123];
int len1, len2, cnt = 0;

int calcLCS(int i,int j)
{
    if(A[i]=='\0' or B[j]=='\0') return 0;
    if(visited[i][j])return dp[i][j];

    int ans=0;
    if(A[i]==B[j]) ans=1+calcLCS(i+1,j+1);
    else
    {
        int val1=calcLCS(i+1,j);
        int val2=calcLCS(i,j+1);
        ans=max(val1,val2);
    }
    visited[i][j]=1;
    dp[i][j]=ans;
    return dp[i][j];
}

void printAll(int i,int j)
{
    if(A[i]=='\0' or B[j]=='\0'){
        if ( sz(v) == 0 || an < v ) v = an;
        return;
    }
    if(A[i]==B[j]){
        an+=A[i];
        printAll(i+1,j+1);
        an.erase(an.end()-1); //Delete last character
    }
    else
    {
        if(dp[i+1][j]>dp[i][j+1]) printAll(i+1,j);
        else if(dp[i+1][j]<dp[i][j+1]) printAll(i,j+1);
        else
        {
            printAll(i+1,j);
            printAll(i,j+1);
        }
    }
    visited[i][j] = 1;
}


int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    For ( i, 1, t+1 ) {
        cin >> A >> B;

        Fill ( visited, 0 );
        Fill ( dp, 0 );
        an.erase ( an.begin(), an.end() );
        v.erase ( v.begin(), v.end() );


        int d = calcLCS ( 0, 0 );
        Fill ( visited, 0 );
        printAll ( 0, 0 );

        cout << "Case " << i << ": " ;
        if ( sz ( v ) == 0 ) cout << ":(";
        else cout << v;
        cout << endl;
    }

    return 0;
}