#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define INF INT_MAX
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define nl "\n"
using namespace std;
const ll MOD = 1e9+7;
const int mxN = 2e5+1;
int main()
{
FAST
//==================
ll t; cin >> t;
while(t--){
ll n , a ; cin >> n>> a;
bool is = 1 ;
ll k = a;
for(int i=2 ;i*i<=k;i++){
while(k%i==0){
k/=i;
is =0;
}
}
if(is || a==1)cout << n << nl;
else{
k = a;
k *= (n/a);
k++;
cout << k << nl;
}
}
}
Copy