#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 5;
const int N = 1e5;
bool isprime[N + 5];
int prime[N + 5], cnt;
void gettable() {
  memset(isprime, 1, sizeof(isprime));
  isprime[1] = 0;
  cnt = 0;
  for (int i = 2; i <= N; i++) {
    if (isprime[i]) prime[cnt++] = i;
    for (int j = 0; j < cnt; j++) {
      long long v = 1ll * i * prime[j];
      if (v > N) break;
      isprime[v] = 0;
      if (i % prime[j] == 0) break;
    }
  }
}
int p[100], m;
vector<int> D[100], d;
set<int> S;
set<int>::iterator iter;
void solve(int n) {
  m = 0;
  int sq = sqrt(n + 0.5);
  int tmp = n;
  for (int i = 0; i < cnt && prime[i] <= min(sq, tmp); i++) {
    if (tmp % prime[i] == 0) {
      p[m++] = prime[i];
      while (tmp % prime[i] == 0) tmp /= prime[i];
    }
  }
  if (tmp > 1) p[m++] = tmp;
  for (int i = 2; i <= sq; i++) {
    if (n % i == 0) {
      int v = n / i;
      if (v != i) d.push_back(v);
      d.push_back(i);
    }
  }
  if (m == 1) {
    for (int i = 0; i < d.size(); i++) cout << d[i] << " ";
    cout << n << '\n';
    cout << 0 << '\n';
    return;
  }
  for (int i = 0; i < d.size(); i++) S.insert(d[i]);
  D[0].push_back(n);
  for (int i = 1; i < m; i++) {
    iter = S.find(p[i - 1]);
    if (iter != S.end()) {
      D[i - 1].push_back(p[i - 1]);
      S.erase(iter);
    }
    int v = p[i - 1] * p[i];
    iter = S.find(v);
    if (iter != S.end()) {
      D[i].push_back(v);
      S.erase(iter);
    }
  }
  for (int i = 0; i < d.size(); i++) {
    if (S.count(d[i])) {
      for (int j = 0; j < m; j++) {
        if (d[i] % p[j] == 0) {
          D[j].push_back(d[i]);
          S.erase(d[i]);
          break;
        }
      }
    }
  }
  d.clear();
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < D[i].size(); j++) {
      d.push_back(D[i][j]);
    }
  }
  for (int i = 0; i < d.size(); i++)
    cout << d[i] << (i < d.size() - 1 ? ' ' : '\n');
  if (m == 2) {
    if (p[0] * p[1] == n)
      cout << 1 << '\n';
    else
      cout << 0 << '\n';
  } else
    cout << 0 << '\n';
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(3);
  gettable();
  int t, n;
  cin >> t;
  while (t--) {
    cin >> n;
    solve(n);
    d.clear();
    for (int i = 0; i < m; i++) D[i].clear();
  }
  return 0;
}
