#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int t, n, cnt = 0, ans = 0, tot = 0, num[maxn] = {}, zz[maxn] = {},
          b[maxn] = {};
vector<int> k[maxn];
int powmod(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) ans = ans * a;
  return ans;
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
void div(int n) {
  int m = n;
  for (int i = 2; i * i <= n; i++) {
    if (m % i == 0) {
      zz[++cnt] = i, num[cnt] = 0;
      while (m % i == 0) m /= i, num[cnt]++;
    }
  }
  if (m > 1) zz[++cnt] = m, num[cnt] = 1;
}
void dfs(int x, int y, int z) {
  if (x > cnt) {
    if (y != 1) k[z].push_back(y);
    return;
  }
  dfs(x + 1, y, z);
  if (z == 0) z = x;
  for (int i = 1; i <= num[x]; i++) dfs(x + 1, y * powmod(zz[x], i), z);
}
void calc() {
  for (int i = 1; i < tot; i++)
    if (gcd(b[i], b[i + 1]) == 1) ans++;
  if (gcd(b[tot], b[1]) == 1) ans++;
}
int main() {
  scanf("%d", &t);
  while (t--) {
    ans = tot = cnt = 0;
    scanf("%d", &n);
    div(n);
    for (int i = 1; i <= cnt; i++) k[i].clear();
    dfs(1, 1, 0);
    for (int i = 1; i <= cnt; i++) {
      int x = -1, y = -1;
      for (int j = 0; j < k[i].size(); j++) {
        if (k[i][j] % zz[((i + cnt - 2) % cnt + cnt) % cnt + 1] == 0) {
          x = k[i][j], k[i].erase(k[i].begin() + j);
          break;
        }
      }
      for (int j = 0; j < k[i].size(); j++) {
        if (k[i][j] % zz[i % cnt + 1] == 0) {
          y = k[i][j], k[i].erase(k[i].begin() + j);
          break;
        }
      }
      if (x != -1) b[++tot] = x;
      for (int j = 0; j < k[i].size(); j++) b[++tot] = k[i][j];
      if (y != -1) b[++tot] = y;
    }
    for (int i = 1; i <= tot; i++) printf("%d ", b[i]);
    calc();
    printf("\n%d\n", ans);
  }
  return 0;
}
