#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 111;
const int MAXC = 1e6 + 111;
const int MOD = 1e9 + 7;
int a[MAXN];
bool was[MAXN];
vector<int> v, d;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int tt;
  cin >> tt;
  for (int t = 0; t < tt; ++t) {
    int n;
    cin >> n;
    v.clear();
    d.clear();
    memset(was, 0, sizeof was);
    for (int i = 2; i * i <= n; ++i) {
      if (n % i == 0) {
        d.push_back(i);
        if (i != n / i) d.push_back(n / i);
      }
    }
    d.push_back(n);
    for (int i = 2; i * i <= n; ++i) {
      int cnt = 0;
      while (n % i == 0) {
        n /= i;
        ++cnt;
      }
      if (cnt > 0) v.push_back(i);
    }
    if (n > 1) v.push_back(n);
    if (v.size() == 2 && d.size() > 3) {
      int last = -1;
      for (int i = 0; i < (int)d.size(); ++i) {
        if (!was[i] && d[i] % v[0] == 0 && d[i] % v[1] == 0 && last == -1) {
          was[i] = true;
          last = d[i];
        }
        if (!was[i] && d[i] % v[0] == 0 && d[i] % v[1] != 0) {
          was[i] = true;
          cout << d[i] << " ";
        }
      }
      for (int i = 0; i < (int)d.size(); ++i) {
        if (!was[i] && d[i] % v[0] == 0 && d[i] % v[1] == 0) {
          was[i] = true;
          cout << d[i] << " ";
        }
      }
      for (int i = 0; i < (int)d.size(); ++i) {
        if (!was[i] && d[i] % v[0] != 0 && d[i] % v[1] == 0) {
          was[i] = true;
          cout << d[i] << " ";
        }
      }
      cout << last << "\n";
      cout << "0\n";
      continue;
    }
    for (int i = 0; i < (int)v.size(); ++i) {
      int nxt = v[(i + 1) % v.size()];
      int prv = v[(i + v.size() - 1) % v.size()];
      for (int j = 0; j < (int)d.size(); ++j) {
        if (!was[j] && d[j] % v[i] == 0 && d[j] != v[i] * nxt &&
            d[j] != v[i] * prv) {
          cout << d[j] << " ";
          was[j] = true;
        }
      }
      if (i == (int)v.size() - 1 && v.size() == 2) continue;
      cout << v[i] * nxt << " ";
    }
    cout << "\n";
    cout << (v.size() == 2 ? "1\n" : "0\n");
  }
  return 0;
}
