#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; #include using namespace std; int main(){ int t; cin>>t; while(t--){ ll a,b; cin>>a>>b; vector B; while(a A; ll n=a; for(ll i=1;i*i<=n;i++){ if(n%i==0){ A.push_back(i); if(i*i!=n) A.push_back(n/i); } } sort(ALL(A)); auto itr=upper_bound(ALL(A),b-a); itr--; a+=*itr; B.push_back(*itr); } cout<