#include <bits/stdc++.h>
using namespace std;
#define MAX 33000
bool p[MAX];
// find prime number upto 33000, we don't need above 33000 because limit of case is 10^7, and 10^7 root is around 32000
void sieve(){
memset(p,0,sizeof(p));
p[0]=1;
p[1]=1;
for(int i=2;i<=MAX;i++){
if(!p[i]){
for(int j=i*i;j<=MAX;j+=i)
p[j]=1;
}
}
}
//find the number of exponent of a prime number if factor is of form a^x * b^y * c^z..., where a,b,c is prime
// It calculates (x+1)*(y+1)*(z+1), The formula I stated in codechef to find number of factor of a number
int process(int n){
int ex=1;
long long ans=1;
if(!(n%2)){
while(!(n%2)){
n/=2;
ex++;
}
}
ans=ans*(ex);
for(int i=3;i*i<=n;i+=2){
if(!p[i] && !(n%i)){
ex=1;
while(!(n%i)){
n/=i;
ex++;
}
ans*=(ex);
}
}
if(n>1) ans*=2;
return ans;
}
// This function checks if number is of power 2, if a number is of power 2 it is of form 10,100,1000,100000 in binary
// that it it will have at most 1 bit as 1 rest will be 0, K&1 checks if a bit is 1 or 0
// if bit is 1 it increments cnt;
// if cnt ==1 , number is of form 10,100,1000,10000 etc etc
// k>>=1 is equivalent to k/2, right shifting the number 10000>>1 will become 1000
bool powerof2(int k){
int cnt=0;
while(k>0){
if(k&1) cnt++;
k>>=1;
}
return cnt==1?1:0;
}
int main() {
// your code goes here
sieve();
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int ans=process(n);
if(powerof2(ans))
cout<<ans<<endl;
else{
bool fl=0;
ans=1;
for(int i=2;i*i<=n;i++){
if(n%i==0){
// if i divides n then n/i is also a factor
// therefore we count factors of n/i and i, if n/i has factors of power 2 we output it
// but in case of i we cannot output as such because if the number is 40, its factors will be (2,20)
// (4,10), (5,8), etc etc
// so we cannot output i as such so we save values of i, until the loop exits, when loop exits we have max of i stored as ans
// which has number of factors of power 2
int a1=process(n/i);
int a2=process(i);
if(powerof2(a1)){
cout<<a1<<endl;
cout<<n/i<<endl;
fl=1;
break;
}
else if(powerof2(a2))
ans=max(ans,a2);
}
}
if(!fl)
cout<<ans<<endl;
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgTUFYIDMzMDAwCmJvb2wgcFtNQVhdOwovLyBmaW5kIHByaW1lIG51bWJlciB1cHRvIDMzMDAwLCB3ZSBkb24ndCBuZWVkIGFib3ZlIDMzMDAwIGJlY2F1c2UgbGltaXQgb2YgY2FzZSBpcyAxMF43LCBhbmQgMTBeNyByb290IGlzIGFyb3VuZCAzMjAwMAp2b2lkIHNpZXZlKCl7CgltZW1zZXQocCwwLHNpemVvZihwKSk7CglwWzBdPTE7CglwWzFdPTE7Cglmb3IoaW50IGk9MjtpPD1NQVg7aSsrKXsKCQlpZighcFtpXSl7CgkJCWZvcihpbnQgaj1pKmk7ajw9TUFYO2orPWkpCgkJCQlwW2pdPTE7CgkJfQoJfQp9CgovL2ZpbmQgdGhlIG51bWJlciBvZiBleHBvbmVudCBvZiBhIHByaW1lIG51bWJlciBpZiBmYWN0b3IgaXMgb2YgZm9ybSBhXnggKiBiXnkgKiBjXnouLi4sIHdoZXJlIGEsYixjIGlzIHByaW1lCi8vIEl0IGNhbGN1bGF0ZXMgKHgrMSkqKHkrMSkqKHorMSksIFRoZSBmb3JtdWxhIEkgc3RhdGVkIGluIGNvZGVjaGVmIHRvIGZpbmQgbnVtYmVyIG9mIGZhY3RvciBvZiBhIG51bWJlcgppbnQgcHJvY2VzcyhpbnQgbil7CglpbnQgZXg9MTsKCWxvbmcgbG9uZyBhbnM9MTsKCWlmKCEobiUyKSl7CgkJd2hpbGUoIShuJTIpKXsKCQkJbi89MjsKCQkJZXgrKzsKCQl9Cgl9CglhbnM9YW5zKihleCk7Cglmb3IoaW50IGk9MztpKmk8PW47aSs9Mil7CgkJaWYoIXBbaV0gJiYgIShuJWkpKXsKCQkJZXg9MTsKCQkJd2hpbGUoIShuJWkpKXsKCQkJCW4vPWk7CgkJCQlleCsrOwoJCQl9CgkJCWFucyo9KGV4KTsKCQl9Cgl9CglpZihuPjEpIGFucyo9MjsKCXJldHVybiBhbnM7Cn0KLy8gVGhpcyBmdW5jdGlvbiBjaGVja3MgaWYgbnVtYmVyIGlzIG9mIHBvd2VyIDIsIGlmIGEgbnVtYmVyIGlzIG9mIHBvd2VyIDIgaXQgaXMgb2YgZm9ybSAxMCwxMDAsMTAwMCwxMDAwMDAgaW4gYmluYXJ5Ci8vIHRoYXQgaXQgaXQgd2lsbCBoYXZlIGF0IG1vc3QgMSBiaXQgYXMgMSByZXN0IHdpbGwgYmUgMCwgSyYxIGNoZWNrcyBpZiBhIGJpdCBpcyAxIG9yIDAKLy8gaWYgYml0IGlzIDEgaXQgaW5jcmVtZW50cyBjbnQ7Ci8vIGlmIGNudCA9PTEgLCBudW1iZXIgaXMgb2YgZm9ybSAxMCwxMDAsMTAwMCwxMDAwMCBldGMgZXRjCi8vIGs+Pj0xIGlzIGVxdWl2YWxlbnQgdG8gay8yLCByaWdodCBzaGlmdGluZyB0aGUgbnVtYmVyIDEwMDAwPj4xIHdpbGwgYmVjb21lIDEwMDAgIApib29sIHBvd2Vyb2YyKGludCBrKXsKCWludCBjbnQ9MDsKCXdoaWxlKGs+MCl7CgkJaWYoayYxKQljbnQrKzsKCQlrPj49MTsKCX0KCXJldHVybiBjbnQ9PTE/MTowOwp9CmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJc2lldmUoKTsKCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKXsKCQlpbnQgbjsKCQljaW4+Pm47CgkJaW50IGFucz1wcm9jZXNzKG4pOwoJCQoJCWlmKHBvd2Vyb2YyKGFucykpCgkJCWNvdXQ8PGFuczw8ZW5kbDsKCQllbHNlewoJCQlib29sIGZsPTA7CgkJCWFucz0xOwoJCQlmb3IoaW50IGk9MjtpKmk8PW47aSsrKXsKCQkJCWlmKG4laT09MCl7CgkJCQkJLy8gaWYgaSBkaXZpZGVzIG4gdGhlbiBuL2kgaXMgYWxzbyBhIGZhY3RvcgoJCQkJCS8vIHRoZXJlZm9yZSB3ZSBjb3VudCBmYWN0b3JzIG9mIG4vaSBhbmQgaSwgaWYgbi9pIGhhcyBmYWN0b3JzIG9mIHBvd2VyIDIgd2Ugb3V0cHV0IGl0CgkJCQkJLy8gYnV0IGluIGNhc2Ugb2YgaSB3ZSBjYW5ub3Qgb3V0cHV0IGFzIHN1Y2ggYmVjYXVzZSBpZiB0aGUgbnVtYmVyIGlzIDQwLCBpdHMgZmFjdG9ycyB3aWxsIGJlICgyLDIwKQoJCQkJCS8vICg0LDEwKSwgKDUsOCksIGV0YyBldGMKCQkJCQkvLyBzbyB3ZSBjYW5ub3Qgb3V0cHV0IGkgYXMgc3VjaCBzbyB3ZSBzYXZlIHZhbHVlcyBvZiBpLCB1bnRpbCB0aGUgbG9vcCBleGl0cywgd2hlbiBsb29wIGV4aXRzIHdlIGhhdmUgbWF4IG9mIGkgc3RvcmVkIGFzIGFucwoJCQkJCS8vIHdoaWNoIGhhcyBudW1iZXIgb2YgZmFjdG9ycyBvZiBwb3dlciAyCgkJCQkJaW50IGExPXByb2Nlc3Mobi9pKTsKCQkJCQlpbnQgYTI9cHJvY2VzcyhpKTsKCQkJCQlpZihwb3dlcm9mMihhMSkpewoJCQkJCQljb3V0PDxhMTw8ZW5kbDsKCQkJCQkJY291dDw8bi9pPDxlbmRsOwoJCQkJCQlmbD0xOwoJCQkJCQlicmVhazsKCQkJCQl9CgkJCQkJZWxzZSBpZihwb3dlcm9mMihhMikpCgkJCQkJCWFucz1tYXgoYW5zLGEyKTsKCQkJCX0KCQkJfQoJCQlpZighZmwpCgkJCQljb3V0PDxhbnM8PGVuZGw7CgkJfQoJfQoJcmV0dXJuIDA7Cn0=