#include<bits/stdc++.h>
#define ll long long
using namespace std;
void slove2(ll n,ll k){
	ll site=1;
	ll round=0;
	ll t;
	while(1){
		round++;
		if(n%k) t=n/k+1;
		else t=n/k;
		n-=t;
		if(n==1) break;
	}
//	printf("%lld\n",round);
	for(int i=1;i<=round;i++){
//		printf("%d %lld\n",i,site);
		if(site%(k-1)) t=site/(k-1)+1;
		else t=site/(k-1);
		site=site+t;
	}
	printf("%lld\n",site);
	return ;
}
ll r[5000010];
void slove1(ll n,ll k){
	ll t;
	ll sumr=0;
	if(n%k) t=n/k+1;
	else t=n/k;
//	printf("t=%lld\n",t);
	for(int i=t;i>=1;i--){
//		printf("i=%d n=%lld\n",i,n);
		r[i]=(n-(k*(i-1)+1))/i+1;
		n-=r[i]*i;
		sumr+=r[i];
	}
	r[1]--;
	sumr--;
//	printf("sumr=%lld\n",sumr);
//	for(int i=1;i<=t;i++){
//		printf("%d %lld\n",i,r[i]);
//	}
    ll site=1;
    ll round=1;
    while(1){
    	ll time;
    	ll x;
    	if(site%(k-1)) x=site/(k-1)+1;
    	else x=site/(k-1);
//    	printf("x=%lld\n",x);
    	ll l=0,r=10000000;
    	while(l+1<r){
    		ll mid=l+r>>1;
    		if(site+mid*x>x*k+1) r=mid;
    		else l=mid;
		}
		time=l;
    	if(time==1){
    		if((site+time*x-1)%k==0){
	    		if(sumr>=1){
		    		sumr-=1;
			    	site+=x+1;
				}
				else {
					break;
				}
			}
	    	else{
	    		if(sumr>=2){
		    		sumr-=2;
			    	site+=x+x+1;
				}
				else{
					site+=x*time;
					break;
				}
			}
		}
    	else if(sumr>=time){
    		if((site+time*x-1)%k==0){
    			site+=time*x+1;
    			sumr-=time;
			}
			else {
				if(sumr>=time+1){
					sumr-=time+1;
		    		site+=time*x+x+1;
				}
				else{
					site+=time*x;
					break;
				}
			}

		}
		else {
			site+=sumr*x;
			break;
		}
//    	printf("site=%lld %lld %lld sum=%lld\n",site,time,x,sumr);
	}
	printf("%lld\n",site);
	
}
void slove(){
	ll n,k;
	scanf("%lld%lld",&n,&k);
	if(n/k>=k) slove2(n,k);
	else 
	slove1(n,k);
	return ;
} 
int main(){
	int T;
	scanf("%d",&T);
	while(T--) slove();
	return 0;
}
/*
4
6 2
8 3
10000 2
1919810 114514
*/