#include <bits/stdc++.h>
using namespace std;
namespace IO {
template <class A, class B>
ostream &operator<<(ostream &out, vector<pair<A, B>> a);
template <class A>
ostream &operator<<(ostream &out, vector<A> a);
template <class A, class B>
ostream &operator<<(ostream &out, pair<A, B> a) {
  out << a.first << " " << a.second;
  return out;
}
template <class A, class B>
ostream &operator<<(ostream &out, vector<pair<A, B>> a) {
  for (pair<A, B> x : a) out << x.first << " " << x.second << '\n';
  return out;
}
template <class A>
ostream &operator<<(ostream &out, vector<A> a) {
  for (A x : a) out << x << ' ';
  return out;
}
template <class A, class B>
istream &operator>>(istream &in, pair<A, B> &a) {
  in >> a.first >> a.second;
  return in;
}
template <class A>
istream &operator>>(istream &in, vector<A> &a) {
  for (A &x : a) in >> x;
  return in;
}
}  // namespace IO
using namespace IO;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<long long> fact(long long n) {
  vector<long long> res;
  long long n2 = n;
  for (long long i = 2; i * i <= n; ++i) {
    while (n2 % i == 0) {
      n2 /= i;
      res.push_back(i);
    }
  }
  if (n2 != 1) res.push_back(n2);
  return res;
}
void solve() {
  long long n;
  cin >> n;
  vector<long long> del;
  for (long long i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      del.push_back(i);
      if (i * i != n) del.push_back(n / i);
    }
  }
  del.push_back(n);
  vector<long long> c = fact(n);
  set<long long> tr(c.begin(), c.end());
  vector<long long> c2(tr.begin(), tr.end());
  map<long long, vector<long long>> res;
  set<long long> ban;
  if (c2.size() == 1) {
    cout << (del) << '\n';
    cout << (0) << '\n';
    return;
  }
  if (c2.size() == 2) {
    for (long long x : del)
      if (x % c2[0] == 0 && x % c2[1] != 0) cout << x << " ";
    vector<long long> c;
    for (long long x : del)
      if (x % c2[0] == 0 && x % c2[1] == 0) c.push_back(x);
    cout << c[0] << " ";
    for (long long x : del)
      if (x % c2[0] != 0 && x % c2[1] == 0) cout << x << " ";
    if (c.size() > 1)
      for (long long i = (1); i < (long long)(c.size()); ++i)
        cout << c[i] << " ";
    cout << ("") << '\n';
    cout << (c.size() > 1 ? 0 : 1) << '\n';
    return;
  }
  for (long long i = (0); i < (long long)(c2.size()); ++i) {
    ban.insert(c2[i] * c2[(i + 1) % c2.size()]);
    res[c2[(i + 1) % c2.size()]].push_back(c2[i] * c2[(i + 1) % c2.size()]);
  }
  for (long long x : del) {
    if (!ban.count(x))
      for (long long j : c2) {
        if (x % j == 0) {
          res[j].push_back(x);
          break;
        }
      }
  }
  for (auto t : res) cout << t.second;
  cout << ("") << '\n';
  cout << (0) << '\n';
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.precision(30);
  long long q = 1;
  cin >> q;
  while (q--) solve();
}
