#include<bits/stdc++.h>
using namespace std;
#define rd(i,n) for(ll i=0;i<n;i++)
#define rp(i,n) for(ll i=1;i<=n;i++)
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define vt vector
#define pb push_back
//#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n,k;
inline int check(ll m){
	ll ans=0;
	while(m>=(__int128)k*k)m-=(m+k-1)/k,ans++;
	while(m>1){
		ll p=(m+k-1)/k,t=(p-1)*k;
		if(p==1)t=1;
		ans+=(m-t+p-1)/p;
		m-=(m-t+p-1)/p*p;
	//	cout<<m<<endl;
	}
	return ans;
}
inline void solve(){
	int res=check(n);
//	cout<<res<<endl;
//	return;
	ll l=1,r=n,mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)==res){
			ans=mid,r=mid-1;
		}else l=mid+1;
	}
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	cin>>n>>k;
	rd(_,t)solve();
    return 0;
}
//Rain Rain Rain;