#include <bits/stdc++.h>
using namespace std;
#define Yalahwy cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);

// alt + ctrl + l
// يا رب
#define ll long long
const ll MOD = 1e9+7;
const ll N = 1e5 + 5;
const ll K = 5;
//const ll M = 100;
double const pi = 3.14159265359;
const int OO=0x3f3f3f3f;
const ll LOO=0x3f3f3f3f3f3f3f3f;
int dx8[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy8[] = {-1, +1, +0, +0, +1, -1, +1, -1};
int dx4[] = {+0, +0, -1, +1};
int dy4[] = {-1, +1, +0, +0};
//struct cmp {
//    bool operator()(M const& p1, M const& p2)
//    {
//        return p1.dis > p2.dis;
//    }
//};
int main() {
    Yalahwy
    ll T = 1;
    cin >> T;
    while (T--) {
        ll a,n;
        cin >> n >> a;
        ll ans = 0;
        for (ll i = max(1LL,n-200)  ; i <= n; ++i) {
            if(__gcd(i,a) == 1 ){
                ans = i;
            }
        }
        ll ans1 = a;
        while(ans1+1 <=n){
            if(__gcd(ans1+1,a) == 1){
                ans = max(ans,ans1+1);
            }
            if(ans1>1e18/a)
                break;
            ans1*=a;
        }
        cout << ans << '\n';
    }
}