#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 ;
}
void slove1(ll n,ll k){
	ll att=(n-1)/k+1;
	ll nn=n;
	ll sum=0;
	for(ll i=att;i>=1;i--){
		if(nn-i<(i-1)*k+1){
//			printf("try i=%lld n=%lld x=%lld\n",i,nn,(nn-1)/k+1);
			if((nn-1)/k+1!=i) continue;
			else{
				nn-=i;
				sum++; 
			}
		}
		else{
			ll l=0,r=1000000000000010ll;
//			printf("down:%lld site=%lld  ",(i-1)*k+1,nn);
			while(l+1<r){
				ll mid=l+r>>1;
				if(nn-i*mid<(i-1)*k+1) r=mid;
				else l=mid;
			}
//			printf("i=%lld r=%lld site=%lld\n",i,r,nn-i*r);
			sum+=r;
			nn-=r*i;
		}
	}
	sum--;
//	printf("sum=%lld\n",sum);
    ll site=1;
    ll addsum=0;
    for(int i=1;i<=att;i++){
//    	printf("i=%lld addsum=%lld sum=%lld  ",i,addsum,sum);
    	if(sum-addsum<=0) break;
    	ll up=i*(k-1);
//    	printf("up=%lld site=%lld\n",up,site,sum);
    	if(site+i>up){
    		ll x;
    		if(site%(k-1)){
    			x=site/(k-1)+1;
			}
			else{
				x=site/(k-1);
			}
    		if(x!=i) continue;
    		else {
    			site+=i;
    			addsum++;
    			continue;
			}
		}
		else{
			ll l=0,r=1000000000000010ll;
			while(l+1<r){
				ll mid=l+r>>1;
				if(site+mid*i<=up) l=mid;
				else r=mid;
			}
//			printf("r=%lld\n",r);
			if(addsum+r>=sum){
				site+=i*(sum-addsum);
				break;
			}
			else{
				addsum+=r;
				site+=i*r;
			}
		}
	}
	printf("%lld\n",site);
	return ;
}
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=1;
	scanf("%d",&T);
	while(T--) slove();
	return 0;
}
/*
4
6 2
8 3
10000 2
1919810 114514
*/