#include <bits/stdc++.h>
using namespace std;
long long min(long long a, long long b) {
  if (a < b) return a;
  return b;
}
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long ab(long long x) {
  if (x > 0) return x;
  return -x;
}
void prtbool(bool x) {
  if (x)
    cout << "YES\n";
  else
    cout << "NO\n";
}
vector<pair<long long, long long> > V;
bool firstprll = false;
long long stored;
void prt(long long x) {
  if (x == 1) return;
  cout << x << " ";
  return;
}
void f(long long x, long long s, long long m, long long m2, long long n) {
  if (x == 1) {
    prt(m * m2);
    prt(m);
    for (long long i = 0, j = m * m2 * m2; i < n - 1; i++, j *= m2) prt(j);
    return;
  }
  for (long long i = s; i * i <= x; i++) {
    if (x % i == 0) {
      long long k = 0;
      while (x % i == 0) x /= i, k++;
      for (long long j = 0; j <= k; j++, m *= i) f(x, i + 1, m, m2, n);
      return;
    }
  }
  prt(m * m2);
  prt(m);
  for (long long i = 0, j = m * m2 * m2; i < n - 1; i++, j *= m2) prt(j);
  prt(m * x * m2);
  prt(m * x);
  for (long long i = 0, j = m * m2 * m2; i < n - 1; i++, j *= m2) prt(j * x);
  return;
}
void g(long long x, long long s, long long m, long long m2) {
  if (x == 1) {
    prt(m * m2);
    return;
  }
  for (long long i = s; i * i <= x; i++) {
    if (x % i == 0) {
      long long k = 0;
      long long tmp = 1;
      while (x % i == 0) x /= i, k++, tmp *= i;
      for (long long j = 0; j <= k; j++, tmp /= i) g(x, i + 1, tmp * m, m2);
      return;
    }
  }
  prt(m * m2);
  prt(m * x * m2);
  return;
}
void test_case() {
  long long X, x;
  cin >> x;
  X = x;
  V.clear();
  firstprll = false;
  stored = 0;
  for (long long i = 2; x != 1 && i * i <= x; i++) {
    pair<long long, long long> t = {i, 0};
    while (x % i == 0) t.second++, x /= i;
    if (t.second != 0) V.push_back(t);
  }
  if (x != 1) {
    pair<long long, long long> t = {x, 1};
    V.push_back(t);
  }
  bool Enpr = false;
  long long v = 0, vn = 0;
  for (auto i : V) {
    Enpr |= (i.second > 1);
    if (i.second > 1) v = i.first, vn = i.second;
  }
  if (Enpr) {
    firstprll = true;
    for (int i = 0; i < vn; i++) X /= v;
    f(X, 2, 1, v, vn);
    cout << "\n0";
  } else {
    reverse(V.begin(), V.end());
    if (V.size() == 2) firstprll = true;
    for (auto i : V) {
      X /= i.first;
      g(X, 2, 1, i.first);
    }
    if (V.size() == 2)
      cout << "\n1";
    else
      cout << "\n0";
  }
  cout << "\n";
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  for (long long i = 0; i < t; i++) test_case();
  return 0;
}
