#include <algorithm>
#include <iostream>
#include <cstring>
#include <complex>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <string>
#include <cmath>
#include <ctime>
#include <queue>
#include <list>
#include <map>
#include <set>
 
#define all(x) (x).begin(), (x).end()
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
 
#ifdef KAZAR
    #define eprintf(...) fprintf(stderr,__VA_ARGS__)
#else
    #define eprintf(...) 0
#endif
 
using namespace std;
 
template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T gcd(T a,T b){return __gcd(a, b);}
template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}
 
const int inf = 1e9 + 143;
const long long longinf = 1e18 + 143;
 
inline int read(){int x;scanf(" %d",&x);return x;}
 
const int N = 55;
 
int n, m;
unsigned a[N][N], res[N][N], t[N][N];
 
void mul(unsigned a[N][N],unsigned b[N][N]){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            t[i][j] = 0;
            for(int k = 0; k < n; k++)
                t[i][j] += a[i][k] * b[k][j];
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            a[i][j] = t[i][j];
}
 
void solve(){
    string alp, s;
    int d = read();
    cin >> alp >> s;
    m = alp.size();
    n = s.size();
    memset(a, 0, sizeof a);
    for(int len = 0; len < n; len++){
        for(int add = 0; add < m; add++){
            string temp = s.substr(0, len);
            temp += alp[add];
            for(int nlen = len + 1; nlen >= 0; nlen--){
                if(nlen == 0 || temp.substr(len + 1 - nlen, nlen) == s.substr(0, nlen)){
                    if(nlen != n)
                        a[len][nlen]++;
                    break;
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            res[i][j] = (i == j)? 1 : 0;
        }
    }
    while(d > 0){
        if(d & 1)
            mul(res, a);
        mul(a, a);
        d >>= 1;
    }
    unsigned ans = 0;
    for(int i = 0; i < n; i++)
        ans += res[0][i];
    cout << ans << endl;
}
 
int main(){
 
#ifdef KAZAR
    freopen("f.input","r",stdin);
    freopen("f.output","w",stdout);
    freopen("error","w",stderr);
#endif
 
    int tc = read();
 
    for(int t = 0; t < tc; t++){
        printf("Case %d: ", t + 1);
        solve();
    }
 
    return 0;
}