#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll n,k;

///返回1~x层的满树有多少结点

ll sum(ll x)

{

    if(x<=) return ;

    if(x==) return ;

    ll ans=;

    for(ll i= ; i<x ; i++)

    {

        ans*=k;ans++;

    }

    return ans;

}

///对于一颗深度为 x 层的满树，返回它的异或值

ll comf(ll x)

{

    if(x<=) return ;

    if(x==) return ;

    ll ans=;

    if(k%==)

    {

       return sum(x);

    }

    else

    {

        ll temp=;

        for(ll i= ; i<=x ; i++)

        {

            temp*=k;

            temp++;

            ans=ans^temp;

        }

    }

    return ans;

}

///对于一颗 k 叉树，返回他的异或值

ll F(ll n)

{

    //printf("520");

    if(n==) return ;

    ll temp=n-;///找到不满的树

    ll L,R;

    ll x=;///层数

    while((temp-)/k>)///防止爆long long

    {

        temp=(temp-)/k;

        x++;

    }

    x++;

    if(n==sum(x)) return comf(x);

    L=temp-;///满k的树有多少棵

    R=k-temp;///缺一层满k的树有多少课

    ll ans=n;

    if(L%==)

    {

        ans=ans^comf(x-);

    }

    if(R%==)

    {

        ans=ans^comf(x-);

    }

    ///不满k树有多少课节点

    n=n-L*sum(x-)-R*sum(x-)-;

    ans=ans^F(n);

    return ans;

}

int main()

{

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

    while(T--)

    {

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

        if(k==)

        printf("%lld\n",n%==?:(n%==?n+:(n%==?:n)));

        else printf("%lld\n",F(n));

    }

}