#include <bits/stdc++.h>
using namespace std;
set<long long> factores;
void fact(int n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      factores.insert(n / i);
      factores.insert(i);
    }
  }
  factores.insert(n);
  return;
}
long long mulMod(long long a, long long b, long long m = 1000000007) {
  long long x = 0, y = a % m;
  while (b > 0) {
    if (b % 2 == 1) x = (x + y) % m;
    y = (y * 2) % m;
    b /= 2;
  }
  return x % m;
}
long long expMod(long long b, long long e, long long m = 1000000007) {
  if (!e) return 1;
  long long q = expMod(b, e / 2, m);
  q = mulMod(q, q, m);
  return e % 2 ? mulMod(b, q, m) : q;
}
bool es_primo_prob(long long n, int a) {
  if (n == a) return true;
  long long s = 0, d = n - 1;
  while (d % 2 == 0) s++, d /= 2;
  long long x = expMod(a, d, n);
  if ((x == 1) || (x + 1 == n)) return true;
  for (int i = (0); i < (s - 1); i++) {
    x = mulMod(x, x, n);
    if (x == 1) return false;
    if (x + 1 == n) return true;
  }
  return false;
}
bool rabin(long long n) {
  if (n == 1) return false;
  const int ar[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
  for (int j = (0); j < (9); j++)
    if (!es_primo_prob(n, ar[j])) return false;
  return true;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  cin >> t;
  for (int T = (0); T < (t); T++) {
    int n;
    cin >> n;
    fact(n);
    vector<pair<int, int> > pares;
    for (auto it = factores.begin(); it != factores.end(); it++) {
      long long auxn = n;
      long long pr = *it;
      long long cont = 0;
      if (rabin(pr)) {
        while (auxn % pr == 0) {
          cont++;
          auxn /= pr;
        }
        pares.push_back(make_pair(pr, cont));
      }
    }
    int tam = ((int)pares.size());
    if (tam == 1) {
      for (auto it = factores.begin(); it != factores.end(); it++)
        cout << *it << " ";
      cout << endl;
      cout << 0 << endl;
    } else if (tam == 2 && pares[0].second == 1 && pares[1].second == 1) {
      for (auto it = factores.begin(); it != factores.end(); it++)
        cout << *it << " ";
      cout << endl;
      cout << 1 << endl;
    } else if (tam == 2) {
      vector<bool> used(((int)factores.size()));
      for (int i = (0); i < (((int)factores.size())); i++) used[i] = 0;
      for (int i = (0); i < (tam); i++) {
        long long no1 = pares[i].first * pares[(i + 1) % tam].first;
        long long no2 = pares[i].first * pares[(i - 1 + tam) % tam].first;
        int cont = 0;
        for (auto it = factores.begin(); it != factores.end(); it++) {
          if (used[cont] == 0 && (*it % pares[i].first == 0) && (*it != no1)) {
            if (*it != no2) cout << *it << " ";
            used[cont] = 1;
          }
          cont++;
        }
        if (i == 1) cout << no1 << " ";
      }
      cout << endl;
      cout << 0 << endl;
    } else {
      vector<bool> used(((int)factores.size()));
      for (int i = (0); i < (((int)factores.size())); i++) used[i] = 0;
      for (int i = (0); i < (tam); i++) {
        long long no1 = pares[i].first * pares[(i + 1) % tam].first;
        long long no2 = pares[i].first * pares[(i - 1 + tam) % tam].first;
        int cont = 0;
        for (auto it = factores.begin(); it != factores.end(); it++) {
          if (used[cont] == 0 && (*it % pares[i].first == 0) && (*it != no1)) {
            if (*it != no2) cout << *it << " ";
            used[cont] = 1;
          }
          cont++;
        }
        cout << no1 << " ";
      }
      cout << endl;
      cout << 0 << endl;
    }
    factores.clear();
  }
  return 0;
}
