#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define min(a,b) ((a<b)?(a):(b))
#define MAXRETRIES (1<<16)
typedef unsigned long long ull;
ull cntm = 0, pcnt;
ull primes[MAXRETRIES];
ull parr[MAXRETRIES * 2];
ull arr[MAXRETRIES];

map < ull, ull > pm;
      map < ull, ull >::iterator it;

#define BAD (0xffffffffffffffffULL)

#define NOTRIES 32

struct mybigi
{
  ull hi, lo;
};

ull GMASK = (0x8000000000000000ULL);

inline mybigi
leftshift (mybigi a)
{
  mybigi tmp;
  tmp = a;
  ull sbit = (tmp.lo & GMASK);
  tmp.hi <<= 1;
  tmp.lo <<= 1;
  if (sbit)
    tmp.hi |= 1;

  return tmp;
}

inline ull
divt (mybigi a, ull d)
{
  mybigi q;
  ull sbit;
  int i;
  ull r = 0;
  q = a;
  for (i = 0; i < 128; i++)
    {
      sbit = (q.hi & GMASK);
      r <<= 1;
      if (sbit)
	r |= 1;
      q = leftshift (q);
      if (r >= d)
	{
	  r -= d;
	  q.lo |= 1;
	}
    }

  //printf("r is %llu\n",r);

  return r;

}

inline mybigi
mult (ull x, ull y)
{
  ull MASK = 0xffffffff;
  ull bits = 32;
  ull a = (x >> bits) & MASK;
  ull b = x & MASK;
  ull c = (y >> bits) & MASK;
  ull d = y & MASK;

  ull lo, u, v, high;
  mybigi t;

  lo = b * d;
  u = a * d + c * b;
  v = ((lo >> bits) & MASK) + u;
  lo = ((lo & MASK) | ((v & MASK) << bits));
  high = (v >> bits) & MASK;
  high += a * c;
  t.hi = high;
  t.lo = lo;
  return t;
}


inline ull
comp (ull x, ull N, ull C)
{
  ull z = x, u = 1ULL;
  x %= N;
  mybigi a = mult (x, x);
  //printf("DEBUG:%llu,%llu\n",a.hi,a.lo);
  ull r = divt (a, N);
  //printf("DEBUG:%llu\n",r);
  return (r + C) % N;
}



inline ull
gcd (ull a, ull b)
{

  if (b == 0)
    return a;

  return gcd (b, a % b);
}

/*
inline ull abs(ull x)
{
	if(x<0)
		x=-x;
	return x;
}
*/


bool
issquare (ull N)
{
  ull z = sqrt (N);
  if (z * z == N)
    return true;

  return false;
}

inline ull
squareroot (ull N)
{
  ull z = sqrt (N);

  if (N == 1 || N == 2 || N == 3)
    return N;

  if (z * z == N)
    {
      if (issquare (z))
	return squareroot (z);
      return z;
    }

  return BAD;

}


inline ull
mypow (ull a, ull b, ull c)
{
  a %= c;
  ull z = a, prod = a, u, x, y, prod1;
  if (b == 0)
    return 1;

  if (b == 1)
    return a;

  if (b & 1)
    z = a;
  else
    z = 1;

  mybigi mp = mult (a, a);
  prod = divt (mp, c);

  u = mypow (prod, b / 2, c) % c;
  mp = mult (z, u);
  return divt (mp, c);
}

bool
ispow2 (ull a)
{
  if (!a)
    return false;
  if (a & (a - 1) == 0)
    return true;
  return false;
}

inline ull
brent (ull n, ull C)
{
  long long y, r, q, m;
  m = 111;
  //for(m=201;m>=1;m--);
  {
//        printf("ENTERING\n");
    y = r = q = 1;

    long long x, ys, k, z, g;
    int i, iter = 0;
    while (++iter < NOTRIES)
      {
	x = y;
//      printf("x=%lld,y = %lld,r=%lld\n",x,y,r);
	for (i = 1; i <= r; i++)
	  {
	    y = comp (y, n, C);
//        printf("^^y is %lld\n",y);
	  }
	k = 0;
//      printf("^^y is %lld\n",y);
	while (++iter < NOTRIES)
	  {
//          printf("r is %lld\n",r);
	    ys = y;
	    long long pp = min (m, r - k);
	    //CORRECT  long long pp=min(m,r-k);
//          printf("#pp is %lld\n",pp);
	    for (i = 1; i <= pp; i++)
	      {
//              printf("i is %lld\n",i);
		y = comp (y, n, C);
		mybigi t;
		z = abs (x - y);
		t = mult (q, z);
		q = divt (t, n);
//              printf("q is %lld\n",q);
//              printf("y is %lld\n",y);
	      }
//          printf("i is %lld\n",i);
	    g = gcd (q, n);
//              printf("g is %lld\n",g);
	    k += m;
//              printf("k is %lld,r=%lld,c=%d\n",k,r,C);
	    if ((k >= r) || (g > 1))
	      break;

	  }
	r *= 2;
	if (g > 1)
	  break;
      }
    iter = 0;
    if (g == n)
      {
	while (++iter < NOTRIES)
	  {
	    ys = comp (ys, n, C);
//          printf("ys is %lld\n",ys);
	    g = gcd (abs (x - ys), n);
//          printf("g is %lld\n",g);
	    if (g > 1)
	      return BAD;
	  }
      }
    if (g > 1 && g < n && (n % g == 0))
      return g;
  }

  return BAD;
}


inline void
genprimes (void)
{
  int i, j;

  for (i = 3; i * i <= MAXRETRIES; i += 2)
    {
      if (parr[i] == 1)
	continue;
      for (j = i; i * j <= MAXRETRIES; j += 2)
	{
	  parr[i * j] = 1;
	}

    }
  primes[pcnt++] = 2;
  for (i = 3; i <= MAXRETRIES; i += 2)
    {
      if (!parr[i])
	primes[pcnt++] = i;
    }

  return;
}

inline ull
factorizegen (ull n)
{
  ull z = (ull)sqrt (n);
  int i;

  for (i = 0; i < pcnt && n > 1 && primes[i] <= z; i++)
    {
      while (n && ((n % primes[i]) == 0))
	{
	  arr[cntm++] = primes[i];
	  n /= primes[i];
	}
    }

  return n;
}

bool isprime1(ull n)
{
	return true;

}

inline bool
isprime (ull n)
{
	ull x=n-1,s=0,d,a,r,z,z1,r2,k,p;
	
	if(n<=MAXRETRIES){
		if(n==2)
			return true;
		if((n&1)==0)
			return false;
		return ((parr[n]==0)?true:false);
	}

	while(x%2==0)
	{
		x/=2;
		s++;
	}
	d=x;

	x=n-1;
	for(k=0;k<10;k++)
	{
		a=primes[k];
		//a=137;
		p=gcd(a,n);
		if(n%a==0)
			return false;
		if(p!=1)
			return false;

//		printf("p is %llu,d=%llu\n",p,d);

                 int flag=0;

		z=mypow(a,d,n);

//		printf("z is %llu\n",z);

		if(z!=1)
			flag=0;
		else
			flag=1;

		for(r=0;r<s ;r++)
		{
			r2=(1LL<<r);
			r2*=d;
			z1=mypow(a,r2,n);
//			printf("r2=%llu,z1=%llu\n",r2,z1);
			if(z1!=n-1)
				flag|=0;
			else
				flag|=1;
		}
		if(!flag)
			return false;
	}
	return true;

}

int
main ()
{
  genprimes ();
  ull n, k;
  long long x;
  int i = 1;
//  printf("%lld\n",gcd(2,123123123))
  int no;
  //scanf(" %llu",&n);
  //printf(" %llu\n",(isprime(n)?1LL:0LL));
  scanf (" %d", &no);
  while (no--)
    {
      scanf (" %lld", &x);


      cntm = 0;
      n = x;
      ull C = 1, k;
      ull z;
      //n=factorizegen(n);

      int some = 0;
  	//printf("isprime %llu\n",(isprime(n)?1LL:0LL));
      if (!isprime (n))
	{
	//printf("ENTERED here\n");
	  n = factorizegen (n);
	//	printf("n is %llu\n",n);
	  for (C = 11; some < 2 && C > 0 && n > 1 && n > (1LL << 32); C--)
	    {
	      z = brent (n, C);
	 //     printf("Z is %llu\n",z);
	      if (z > 1 && (z != BAD) && (z != n))
		{
		  while (n > 1 && (n % z == 0))
		    {
		      if (!isprime (z)){
			k = factorizegen (z);
		      }
		      else
			k = z;
		      if (k > 1)
			arr[cntm++] = k;
		      n /= z;
		    }
		}
	      else
		some++;
	    }

	  if (n > 1)
	    {
	      if (!isprime (n)){
		n = factorizegen (n);
	      }
	      if (isprime (n))
		arr[cntm++] = n;

	    }
	}
      else
	arr[cntm++] = n;

      //printf("cntm is %llu\n",cntm);

      //sort (arr, arr + cntm);
      //


      pm.clear ();
      for (i = 0; i < cntm; i++)
	{
//		printf("%llu\n",arr[i]);
	  pm[arr[i]]++;
	}

      ull numprod, denprod, gg;
      numprod = denprod = 1;
      for (it = pm.begin (); it != pm.end (); it++)
	{
	  ull a = it->first, b = it->second;
	  ull num= (ull) (pow (( double) a, (double) b + 1) - 1);
	  ull den=a-1;
	  gg=gcd(num,den);
	  num/=gg;
	  den/=gg;
	  numprod *=num;
	  denprod *=den;
	  gg = gcd (numprod, denprod);
	  numprod /= gg;
	  denprod /= gg;
	}

      gg = gcd (numprod, denprod);
      numprod /= gg;
      denprod /= gg;





      printf ("%llu\n", numprod - x);
    }

  return 0;
}