#include <bits/stdc++.h>
using namespace std;
const long long INF = 9e18;
const int inf = 2147483647;
long long qpow(long long a, long long b, long long mod) {
  long long r = 1;
  for (; b; b >>= 1) {
    if (b & 1) r = (r * a) % mod;
    a = (a * a) % mod;
  }
  return r;
}
const int N = 1e5 + 5;
vector<int> a;
set<int> c;
void look(int n) {
  a.clear();
  int q = sqrt(n + 0.5);
  for (int i = 2; i <= q; i++) {
    if (n % i == 0) {
      a.push_back(i);
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) a.push_back(n);
}
void lck(int n) {
  c.clear();
  int q = sqrt(n + 0.5);
  for (int i = 2; i <= q; i++) {
    if (n % i == 0) {
      c.insert(i);
      c.insert(n / i);
    }
  }
  c.insert(n);
}
void work() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    look(n);
    lck(n);
    if (a.size() == 2) {
      int cnt = 0, ans[2] = {0};
      for (auto &it : c) {
        if (it > a[1] && it % a[1] == 0) {
          if (cnt == 1) {
            if (ans[0] % a[0] && it % a[0]) continue;
          }
          ans[cnt++] = it;
          if (cnt >= 2) break;
        }
      }
      if (cnt >= 2) {
        c.erase(a[0]);
        c.erase(a[1]);
        for (int i = 0; i < 2; i++) c.erase(ans[i]);
        printf("%d ", a[0]);
        for (auto &it : c) printf("%d ", it);
        if (ans[0] % a[0] == 0) swap(ans[1], ans[0]);
        printf("%d ", ans[0]);
        printf("%d ", a[1]);
        printf("%d ", ans[1]);
        puts("");
        printf("%d\n", 0);
      } else {
        c.erase(a[0]), c.erase(a[1]);
        printf("%d ", a[0]);
        for (auto &it : c) printf("%d ", it);
        printf("%d ", a[1]);
        puts("");
        printf("%d\n", 1);
      }
    } else {
      queue<int> v;
      for (int i = 0; i < a.size() - 1; i++) {
        v.push(a[i] * a[i + 1]);
        c.erase(a[i] * a[i + 1]);
      }
      v.push(a[0] * a[a.size() - 1]);
      c.erase(a[0] * a[a.size() - 1]);
      for (auto &it : a) {
        printf("%d ", it);
        c.erase(it);
        vector<int> b;
        for (auto &ans : c) {
          if (ans % it == 0) {
            b.push_back(ans);
          }
        }
        for (auto &ans : b) {
          printf("%d ", ans);
          c.erase(ans);
        }
        printf("%d ", v.front());
        v.pop();
      }
      puts("");
      printf("%d\n", 0);
    }
  }
}
int main() {
  work();
  return 0;
}
