#include<cstdio>

using namespace std;

typedef long long ll;

ll n,K,pw[105];

int T;

int main(){

//	freopen("1002.in","r",stdin);

//	freopen("1002.out","w",stdout);

	scanf("%d",&T);

	for(;T;--T){

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

		if(K==1){

			if(n%4ll==0){

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

			}

			else if(n%4ll==1ll){

				printf("%lld\n",1ll);

			}

			else if(n%4ll==2ll){

				printf("%lld\n",n+1ll);

			}

			else{

				printf("%lld\n",0ll);

			}

			continue;

		}

		pw[0]=1;

		int j;

		for(j=1;pw[j-1]<=n/K;++j){

			pw[j]=pw[j-1]*K;

		}

		--j;

		int e=j;

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

			if(pw[k-1]>n-pw[k]){

				e=k-1;

				break;

			}

			pw[k]+=pw[k-1];

		}

		if(n==pw[e]){

			--e;

		}

		ll i=n-1ll;

		ll now=n;

		ll nowsiz=1,sumnowsiz=1;

		ll ans=1;

		ll sheng=((n-pw[e])%K!=0 ? (n-pw[e])%K : K);

		int E=e;

		while(i!=0){

			ll fa=(i-1)/K;

			if((i-1ll-fa)%2ll==1ll){

				ans^=sumnowsiz;

			}

			ans^=(sumnowsiz+sheng);

			now=pw[e];

			--e;

			i=fa;

			nowsiz*=K;

			sumnowsiz+=nowsiz;

			sheng=((n-pw[E])%(nowsiz*K)!=0 ? (n-pw[E])%(nowsiz*K) : (nowsiz*K));

		}

		printf("%lld\n",ans);

	}

	return 0;

}