#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define cout2(x, y) cout << x << " " << y << endl
#define N 200004
#define MOD 1000000007
using namespace std;
long long getSqrt(long long n){
long long lo = 1, hi = 1000000000, me;
while(lo < hi){
me = lo + (hi - lo + 1)/2;
if(me * me > n)hi = me - 1;
else lo = me;
}
if(lo * lo != n)return -1;
return lo;
}
int main(){
int tc = 0, limit = 1000009;
scanf("%d", &tc);
while(tc--){
long long n, phi;
scanf("%lld%lld", &n, &phi);
vector<long long>ans;
for(long long i = 2; i <= limit; i++){
if(n%i == 0){
long long p = 1;
while(n%i == 0)p *= i, n /= i, ans.pb(i);
phi = phi/(p - p/i);
}
}
if(n > 1){
long long sqrt = getSqrt(n);
if(sqrt != -1)ans.pb(sqrt), ans.pb(sqrt);
else{
if(phi == n - 1)ans.pb(n);
else{
long long c = n + 1 - phi, r = getSqrt(c * c - 4 * n);
long long p1 = (c + r)/2;
long long p2 = (c - r)/2;
if(n%p1 == 0)ans.pb(p1), ans.pb(n/p1);
else if(n%p2 == 0)ans.pb(p2), ans.pb(n/p2);
}
}
}
sort(all(ans));
printf("%lld", ans[0]);
for(int i = 1; i < ans.size(); i++)printf(" %lld", ans[i]);
puts("");
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBwYih4KSBwdXNoX2JhY2soeCkKI2RlZmluZSBhbGwoeCkgeC5iZWdpbigpLCB4LmVuZCgpCiNkZWZpbmUgY291dDIoeCwgeSkgY291dCA8PCB4IDw8ICIgIiA8PCB5IDw8ICBlbmRsCiNkZWZpbmUgTiAyMDAwMDQKI2RlZmluZSBNT0QgMTAwMDAwMDAwNwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmxvbmcgbG9uZyBnZXRTcXJ0KGxvbmcgbG9uZyBuKXsKCQoJbG9uZyBsb25nIGxvID0gMSwgaGkgPSAxMDAwMDAwMDAwLCBtZTsJCQoJd2hpbGUobG8gPCBoaSl7CgkJCgkJbWUgPSBsbyArIChoaSAtIGxvICsgMSkvMjsKCQlpZihtZSAqIG1lID4gbiloaSA9IG1lIC0gMTsKCQllbHNlIGxvID0gbWU7Cgl9CgkKCWlmKGxvICogbG8gIT0gbilyZXR1cm4gLTE7CglyZXR1cm4gbG87Cn0KCmludCBtYWluKCl7CgoJaW50IHRjID0gMCwgbGltaXQgPSAxMDAwMDA5OwoJc2NhbmYoIiVkIiwgJnRjKTsKCQoJd2hpbGUodGMtLSl7CgkJCgkJbG9uZyBsb25nIG4sIHBoaTsKCQlzY2FuZigiJWxsZCVsbGQiLCAmbiwgJnBoaSk7CgkJCgkJdmVjdG9yPGxvbmcgbG9uZz5hbnM7CgkJZm9yKGxvbmcgbG9uZyBpID0gMjsgaSA8PSBsaW1pdDsgaSsrKXsKCQkJCgkJCWlmKG4laSA9PSAwKXsKCQkJCQoJCQkJbG9uZyBsb25nIHAgPSAxOwoJCQkJd2hpbGUobiVpID09IDApcCAqPSBpLCBuIC89IGksIGFucy5wYihpKTsKCQkJCXBoaSA9IHBoaS8ocCAtIHAvaSk7CgkJCX0KCQl9CgkJCgkJaWYobiA+IDEpewoKCQkJbG9uZyBsb25nIHNxcnQgPSBnZXRTcXJ0KG4pOwoJCQlpZihzcXJ0ICE9IC0xKWFucy5wYihzcXJ0KSwgYW5zLnBiKHNxcnQpOwoJCQllbHNlewoJCQkJCgkJCQlpZihwaGkgPT0gbiAtIDEpYW5zLnBiKG4pOwoJCQkJZWxzZXsKCQkJCQkKCQkJCQlsb25nIGxvbmcgYyA9IG4gKyAxIC0gcGhpLCByID0gZ2V0U3FydChjICogYyAtIDQgKiBuKTsKCQkJCQkKCQkJCQlsb25nIGxvbmcgcDEgPSAoYyArIHIpLzI7CgkJCQkJbG9uZyBsb25nIHAyID0gKGMgLSByKS8yOwoJCQkJCQoJCQkJCWlmKG4lcDEgPT0gMClhbnMucGIocDEpLCBhbnMucGIobi9wMSk7CgkJCQkJZWxzZSBpZihuJXAyID09IDApYW5zLnBiKHAyKSwgYW5zLnBiKG4vcDIpOwoJCQkJCQoJCQkJfQkKCQkJfQoJCQkKCQl9CgkJCgkJc29ydChhbGwoYW5zKSk7CgkJcHJpbnRmKCIlbGxkIiwgYW5zWzBdKTsKCQlmb3IoaW50IGkgPSAxOyBpIDwgYW5zLnNpemUoKTsgaSsrKXByaW50ZigiICVsbGQiLCBhbnNbaV0pOwoJCXB1dHMoIiIpOwoJfQp9CgoKCg==