#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

const int N = 1e6+7;

typedef long long ll;

typedef __int128 bll;

const ll mod = 998244353;

using namespace std;

inline __int128 read() {

     __int128 x=0,f=1;

     char ch=getchar();

     while(ch<'0'||ch>'9') {

         if(ch=='-')

             f=-1;

         ch=getchar();

     }

     while(ch>='0'&&ch<='9') {

         x=x*10+ch-'0';

         ch=getchar();

     }

     return x*f;

}

inline void print(__int128 x)

{

   if(x<0){putchar('-');x=-x;}

   if(x>9) print(x/10);

   putchar(x%10+'0');

}

bll dp[30][30][30];

char v[30];

bll dfs(int len,int now,int mx){

    if(now==len){

        dp[len][now][mx]=1;

        return dp[len][now][mx];

    }

    if(dp[len][now][mx]!=-1) return dp[len][now][mx];

    bll ans=0;

    for(int i=1;i<=min(mx+1,26);i++){

        if(i<=mx){

            ans+=dfs(len,now+1,mx);

        }else{

            ans+=dfs(len,now+1,i);

        }

    }

    dp[len][now][mx]=ans;

    return ans;

}

int main(){

//    ios::sync_with_stdio(false);

//    cin.tie(0); cout.tie(0);

    int t; scanf("%d",&t);

    for(int i=0;i<30;i++)

        for(int j=0;j<30;j++)

            for(int k=0;k<30;k++)

                dp[i][j][k]=-1;

    for(int i=1;i<=26;i++)

        dfs(i,1,1);

    int w=0;

//    print(dp[3][1][1]);

    while(t--){

        int n; scanf("%d",&n);

        bll k; k=read();

        int mx=1;

        printf("Case #%d: ",++w);

        for(int i=1;i<=n;i++){

            v[i]='A';

            for(int j=1;j<=mx+1;j++){

                //cout<<k<<" "<<dp[n][i][j]<<endl;

                int p=max(mx,j);

                if(dp[n][i][p]>=k){

                //    mx=max(mx,j);

                    v[i]=char(j+'A'-1);

                    //putchar('A' + j - 1);

                    mx=max(mx,p);

                //    cout<<j<<endl;

                    break;

                }else{

                    k-=dp[n][i][p];

                }

            }

        }

        for(int i=1;i<=n;i++)

            printf("%c",v[i]);

        puts("");

    }

    return 0;

}