#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#define N 100010

#define mod 1000000007

#define LL long long

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

int n,k;

int sum[N<<],vis[N];

void Pushup(int rt)

{

    int ls=rt<<,rs=ls|;

    sum[rt]=sum[ls]+sum[rs];

}

void build(int l,int r,int rt)

{

    if(l==r)

    {

        sum[rt]=;return;

    }

    int m=(l+r)>>;

    build(lson);

    build(rson);

    Pushup(rt);

}

void update(int num,int l,int r,int rt)

{

    if(l==r)

    {

        vis[l]=;

        sum[rt]=;

        return;

    }

    int m=(l+r)>>;

    if(num<=sum[rt<<])update(num,lson);

    else update(num-sum[rt<<],rson);

    Pushup(rt);

}

int main()

{

    int T,cas=;

    scanf("%d",&T);

    while(T--)

    {

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

        memset(vis,,sizeof(vis));

        build(,n,);

        int num=;

        for(int i=n;i>;i--)

        {

            num=(num+k-)%i;

            if(num==)num=i;

            update(num,,n,);

        }

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

        if(!vis[i])

        {

            printf("Case %d: %d\n",cas++,i);break;

        }

    }

}