#include <bits/stdc++.h> #define ll long long using namespace std; inline ll read(){ register ll x(0); register char c(getchar()); register short w(1); for (;c < '0' || c > '9';c = getchar()) if (c == '-') w = -1; for (;c >= '0' && c <= '9';c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); return x * w; } int t; int main(){ ios::sync_with_stdio(false); t = read(); for (;t--;){ ll n(read()),p(read());bool flag(false); if (p == 1) { cout << 1 << endl; continue; } if (n * (n - 1) % p == 0){ if (n % p == 0) cout << 1 << endl; else cout << n - 1 << endl; continue; } if (n == 2 && p % 2 == 1){ cout << (p - n) * p / 2 << endl; continue; } for (int i(2);i <= sqrt(n);i++) if (n % i == 0) { cout << 1 << endl; flag = true; break; } else if ((n - 1) % i == 0) { cout << n - i << endl; flag = true; break; } else { cout << i << endl; flag = true; break; } if (flag) continue; cout << -1 << endl; } return 0; }