#include<bits/stdc++.h>
using namespace std;
int t;
long long x, z;

inline long long read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

long long gcd(long long a, long long b){
  if(a == 0){
    return b;
  }
  if(b == 0){
    return a;
  }
  if(!(a & 1) && !(b & 1)){
    return gcd(a >> 1, b >> 1) << 1;
  }
  else if(!(b & 1)){
    return gcd(a, b >> 1);
  }
  else if(!(a & 1)){
    return gcd(a >> 1, b);
  }
  else{
    return gcd(abs(a - b), min(a, b));
  }
}

int main(){
  freopen("math.in", "r", stdin);
  freopen("math.out", "w", stdout);
  t = read();
  while(t--){
    x = read();
    z = read();
    long long num = z / x, y = 0;
    bool f = 0;
    for(long long i = 1;i <= num;i++){
      if(num % i == 0){
        y = num / i;
        if(i == gcd(x, y)){
          cout << y << endl;
          f = 1;
          break;
        }
      }
    }
    if(!f){
      cout << -1 << endl;
    }
  }
  return 0;
}