#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


#ifndef LIBRA_OTHER_INT128_H_
#define LIBRA_OTHER_INT128_H_

#include <stdio.h>
#include <iostream>

constexpr unsigned __int128 toUInt128(const char *s) {
  unsigned __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
constexpr __int128 toInt128(const char *s) {
  if (*s == '-') return -toInt128(s + 1);
  __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
unsigned __int128 inUInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toUInt128(buf);
}
__int128 inInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toInt128(buf);
}

void out(unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) putchar(buf[i]);
}
void out(__int128 x) {
  if (x < 0) {
    putchar('-');
    out(-static_cast<unsigned __int128>(x));
  } else {
    out(static_cast<unsigned __int128>(x));
  }
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) os << buf[i];
  return os;
}
std::ostream &operator<<(std::ostream &os, __int128 x) {
  if (x < 0) {
    os << '-' << -static_cast<unsigned __int128>(x);
  } else {
    os << static_cast<unsigned __int128>(x);
  }
  return os;
}

#endif  // LIBRA_OTHER_INT128_H_


#ifndef LIBRA_ALGEBRA_MODINT128_H_
#define LIBRA_ALGEBRA_MODINT128_H_

#include <assert.h>
#include <iostream>

// #include "../other/int128.h"

////////////////////////////////////////////////////////////////////////////////
// floor(a b / 2^128)
inline unsigned __int128 mul128High(unsigned __int128 a, unsigned __int128 b) {
  const unsigned __int128 a0 = static_cast<unsigned long long>(a), a1 = a >> 64;
  const unsigned __int128 b0 = static_cast<unsigned long long>(b), b1 = b >> 64;
  return ((((a0 * b0) >> 64) + static_cast<unsigned long long>(a0 * b1) + static_cast<unsigned long long>(a1 * b0)) >> 64) + ((a0 * b1) >> 64) + ((a1 * b0) >> 64) + a1 * b1;
}

// Hold y := (2^128 x) mod M
template <int ID> struct RMModInt128 {
  static unsigned __int128 M;
  static unsigned __int128 INV_M;  // M^-1 mod 2^128
  static unsigned __int128 TWO256;  // 2^256 mod M
  static void setM(unsigned __int128 m) {
    assert(m & 1); assert(1 <= m); assert(!(m >> 127));
    M = m;
    INV_M = (3 * M) ^ 2;
    for (int i = 0; i < 5; ++i) INV_M *= (2 - M * INV_M);
    TWO256 = (-M) % M;
    for (int i = 0; i < 128; ++i) TWO256 = ((TWO256 <<= 1) >= M) ? (TWO256 - M) : TWO256;
  }
  // (2^-128 a) mod M  (0 <= a < 2^128 m)
  static inline unsigned __int128 reduce(unsigned __int128 a) {
    const unsigned __int128 c = -mul128High(INV_M * a, M);
    return (c >= M) ? (c + M) : c;
  }
  // (2^-128 a b) mod M  (0 <= a b < 2^128 m)
  static inline unsigned __int128 mulReduce(unsigned __int128 a, unsigned __int128 b) {
    const unsigned __int128 c = mul128High(a, b) - mul128High(INV_M * (a * b), M);
    return (c >= M) ? (c + M) : c;
  }

  unsigned __int128 y;
  RMModInt128() : y(0U) {}
  RMModInt128(unsigned x_) : y(mulReduce(TWO256, x_ % M)) {}
  RMModInt128(unsigned long long x_) : y(mulReduce(TWO256, x_ % M)) {}
  RMModInt128(unsigned __int128 x_) : y(mulReduce(TWO256, x_ % M)) {}
  RMModInt128(int x_) : y(mulReduce(TWO256, ((x_ %= static_cast<__int128>(M)) < 0) ? (x_ + static_cast<__int128>(M)) : x_)) {}
  RMModInt128(long long x_) : y(mulReduce(TWO256, ((x_ %= static_cast<__int128>(M)) < 0) ? (x_ + static_cast<__int128>(M)) : x_)) {}
  RMModInt128(__int128 x_) : y(mulReduce(TWO256, ((x_ %= static_cast<__int128>(M)) < 0) ? (x_ + static_cast<__int128>(M)) : x_)) {}
  unsigned __int128 get() const { return reduce(y); }
  RMModInt128 &operator+=(const RMModInt128 &a) { y = ((y += a.y) >= M) ? (y - M) : y; return *this; }
  RMModInt128 &operator-=(const RMModInt128 &a) { y = ((y -= a.y) >= M) ? (y + M) : y; return *this; }
  RMModInt128 &operator*=(const RMModInt128 &a) { y = mulReduce(y, a.y); return *this; }
  RMModInt128 &operator/=(const RMModInt128 &a) { return (*this *= a.inv()); }
  template <class T> RMModInt128 pow(T e) const {
    if (e < 0) return inv().pow(-e);
    for (RMModInt128 a = *this, b = 1U; ; a *= a) { if (e & 1) { b *= a; } if (!(e >>= 1)) { return b; } }
  }
  RMModInt128 inv() const {
    unsigned __int128 a = M, b = reduce(reduce(y)); __int128 u = 0, v = 1;
    for (; b; ) { const unsigned __int128 q = a / b; const unsigned __int128 c = a - q * b; a = b; b = c; const __int128 w = u - static_cast<__int128>(q) * v; u = v; v = w; }
    assert(a == 1U); RMModInt128 r; r.y = u; r.y = (r.y >= M) ? (r.y + M) : r.y; return r;
  }
  RMModInt128 operator+() const { return *this; }
  RMModInt128 operator-() const { RMModInt128 a; a.y = y ? (M - y) : 0U; return a; }
  RMModInt128 operator+(const RMModInt128 &a) const { return (RMModInt128(*this) += a); }
  RMModInt128 operator-(const RMModInt128 &a) const { return (RMModInt128(*this) -= a); }
  RMModInt128 operator*(const RMModInt128 &a) const { return (RMModInt128(*this) *= a); }
  RMModInt128 operator/(const RMModInt128 &a) const { return (RMModInt128(*this) /= a); }
  template <class T> friend RMModInt128 operator+(T a, const RMModInt128 &b) { return (RMModInt128(a) += b); }
  template <class T> friend RMModInt128 operator-(T a, const RMModInt128 &b) { return (RMModInt128(a) -= b); }
  template <class T> friend RMModInt128 operator*(T a, const RMModInt128 &b) { return (RMModInt128(a) *= b); }
  template <class T> friend RMModInt128 operator/(T a, const RMModInt128 &b) { return (RMModInt128(a) /= b); }
  explicit operator bool() const { return y; }
  bool operator==(const RMModInt128 &a) const { return (y == a.y); }
  bool operator!=(const RMModInt128 &a) const { return (y != a.y); }
  friend std::ostream &operator<<(std::ostream &os, const RMModInt128 &a) { return os << get(); }
};
template <int ID> unsigned __int128 RMModInt128<ID>::M;
template <int ID> unsigned __int128 RMModInt128<ID>::INV_M;
template <int ID> unsigned __int128 RMModInt128<ID>::TWO256;
////////////////////////////////////////////////////////////////////////////////

#endif  // LIBRA_ALGEBRA_MODINT128_H_


using RMM128ForPrime = RMModInt128<-20220617>;

template <class T> vector<T> merge(const vector<T> &a, const vector<T> &b) {
  vector<T> c(a.size() + b.size());
  std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
  return c;
}

int bsf128(__int128 a) {
  const long long a64 = a;
  return a64 ? __builtin_ctzll(a64) : (64 + __builtin_ctzll(a >> 64));
}
__int128 gcd128(__int128 a, __int128 b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  if (a == 0) return b;
  if (b == 0) return a;
  const int s = bsf128(a | b);
  a >>= bsf128(a);
  do {
    b >>= bsf128(b);
    if (a > b) swap(a, b);
    b -= a;
  } while (b);
  return a << s;
}

// Checks if n is a prime using Miller-Rabin test
bool isPrime128(__int128 n) {
  if (n <= 1 || !(n & 1)) return (n == 2);
  RMM128ForPrime::setM(n);
  const int s = bsf128(n - 1);
  const __int128 d = (n - 1) >> s;
  // Based on conjectures in Zhang, Two kinds of strong pseudoprimes up to 10^36.
  for (const __int128 base : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                              31, 37, 41, 43, 47, 53, 59, 61, 67, 71}) {
    if (base >= n) continue;
    RMM128ForPrime a = RMM128ForPrime(base).pow(d);
    if (a.get() == 1 || static_cast<__int128>(a.get()) == n - 1) continue;
    bool ok = false;
    for (int i = 0; i < s - 1; ++i) {
      if (static_cast<__int128>((a *= a).get()) == n - 1) {
        ok = true;
        break;
      }
    }
    if (!ok) return false;
  }
  return true;
}

// Factorize n using Pollard's rho algorithm
vector<__int128> factorize128(__int128 n) {
  static constexpr int BLOCK = 256;
  if (n <= 1) return {};
  if (isPrime128(n)) return {n};
  if (!(n & 1)) {
    const int s = bsf128(n);
    return merge(vector<__int128>(s, 2), factorize128(n >> s));
  }
  RMM128ForPrime::setM(n);
  for (__int128 c0 = 2; ; ++c0) {
    const RMM128ForPrime c = c0;
    RMM128ForPrime x, y = 2, y0, z = 1;
    __int128 d = 1;
    for (int l = 1; d == 1; l <<= 1) {
      x = y;
      for (int i = 0; i < l; ++i) y = y * y + c;
      for (int i = 0; i < l; i += BLOCK) {
        y0 = y;
        for (int j = 0; j < BLOCK && j < l - i; ++j) {
          y = y * y + c;
          z *= (y - x);
        }
        if ((d = gcd128(z.y, n)) != 1) break;
      }
    }
    if (d == n) {
      for (y = y0; ; ) {
        y = y * y + c;
        if ((d = gcd128((y - x).y, n)) != 1) break;
      }
    }
    if (d != n) return merge(factorize128(d), factorize128(n / d));
  }
}

////////////////////////////////////////////////////////////////////////////////


unsigned xrand() {
  static unsigned x = 314159265, y = 358979323, z = 846264338, w = 327950288;
  unsigned t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
}


using Int = __int128;
using Mint = RMModInt128<0>;

constexpr int SMALL = 1'000'000;
int lpf[SMALL];
int primesLen;
int primes[SMALL];

Int M;
Int M0;
int E;

// find at least prime factors of x
vector<Int> ps;
void solve(Int n) {
  if (n <= 1) {
    return;
  }
  if (isPrime128(n)) {
    ps.push_back(n);
    return;
  }
  
  // prime power ==> (>10^6)^(<=6)
  for (int e = 2; e <= 6; ++e) {
    auto pw = [&](Int x) -> Int {
      Int ret = 1;
      for (int f = 0; f < e; ++f) ret *= x;
      return ret;
    };
    Int lo = 0, hi = pow(3.0e36L, 1.0L / e);
    for (; lo + 1 < hi; ) {
      const Int mid = (lo + hi) / 2;
      ((pw(mid) <= n) ? lo : hi) = mid;
    }
    if (pw(lo) == n) {
      solve(lo);
      return;
    }
  }
  
  Mint::setM(n);
  for (; ; ) {
    unsigned __int128 rnd = 0;
    rnd = rnd << 32 | (unsigned __int128)xrand();
    rnd = rnd << 32 | (unsigned __int128)xrand();
    rnd = rnd << 32 | (unsigned __int128)xrand();
    rnd = rnd << 32 | (unsigned __int128)xrand();
    const Mint a = rnd;
    if (gcd128(a.get(), n) != 1) {
      continue;
    }
    // a^(2^e M)
    vector<Mint> bs(E + 1);
    bs[0] = a.pow(M0);
    for (int e = 0; e < E; ++e) {
      bs[e + 1] = bs[e] * bs[e];
    }
    assert(bs[E].get() == 1);
    for (int e = 0; e < E; ++e) {
      if (bs[e + 1].get() == 1) {
        // bs[e]^2 == 1  (mod n)
        const Int d = gcd128((bs[e] - 1).get(), n);
        if (d != 1 && d != n) {
          solve(d);
          solve(n / d);
          return;
        }
      }
    }
  }
}

int main() {
  iota(lpf, lpf + SMALL, 0);
  for (int p = 2; p < SMALL; ++p) if (lpf[p] == p) {
    primes[primesLen++] = p;
    for (int n = 2 * p; n < SMALL; n += p) chmin(lpf[n], p);
  }
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    M = 2 * inInt128();
    
    M0 = M;
    E = 0;
    for (; !(M0 & 1); M0 >>= 1, ++E) {}
    
    ps.clear();
    {
      Int m = M;
      for (int i = 0; i < primesLen; ++i) {
        const int p = primes[i];
        if (m % p == 0) {
          ps.push_back(p);
          do {
            m /= p;
          } while (m % p == 0);
        }
      }
      solve(m);
    }
// cerr<<"ps = "<<ps<<endl;
    reverse(ps.begin(), ps.end());
    
    Int ans = 1;
    {
      Int m = M;
      for (const Int p : ps) {
        if (m % p == 0) {
          int e = 0;
          do {
            ++e;
            m /= p;
          } while (m % p == 0);
          assert(e % 2 != 0);
          // ans: p^((e+1)/2)
          // phi(ans): p^((e-1)/2) (p-1)
          for (int i = 0; i < (e + 1) / 2; ++i) {
            ans *= p;
          }
          assert(m % (p - 1) == 0);
          m /= (p - 1);
        }
      }
    }
    outInt128(ans);
    puts("");
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

answer.code: In function ‘int main()’:
answer.code:402:5: error: ‘outInt128’ was not declared in this scope; did you mean ‘toUInt128’?
  402 |     outInt128(ans);
      |     ^~~~~~~~~
      |     toUInt128
answer.code: In function ‘__int128 unsigned inUInt128()’:
answer.code:54:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   54 |   scanf("%s", buf);
      |   ~~~~~^~~~~~~~~~~
answer.code: In function ‘__int128 inInt128()’:
answer.code:59:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |   scanf("%s", buf);
      |   ~~~~~^~~~~~~~~~~