#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], v[maxn], cnt;
void getprime() {
  for (int i = 2; i <= maxn; i++) {
    if (!v[i]) a[++cnt] = i;
    for (int j = 1; j <= cnt && 1ll * i * a[j] < maxn; j++) {
      v[i * a[j]] = 1;
      if (!(i % a[j])) break;
    }
  }
}
int main() {
  getprime();
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    map<int, int> mp;
    vector<int> prime;
    vector<int> div;
    for (int i = 2; i <= sqrt(n); i++) {
      if (n % i == 0) {
        div.push_back(i);
        if (n / i != i) div.push_back(n / i);
      }
    }
    div.push_back(n);
    sort(div.begin(), div.end());
    int tmp = n;
    for (int i = 1; i <= cnt; i++) {
      if (a[i] > tmp) break;
      if (!(tmp % a[i])) {
        prime.push_back(a[i]);
        while (!(tmp % a[i])) tmp /= a[i];
      }
    }
    if (tmp > 1) prime.push_back(tmp);
    sort(prime.begin(), prime.end());
    if (prime.size() == 1) {
      for (int i = 0; i < div.size(); i++) printf("%d ", div[i]);
      puts("\n0");
    } else if (prime.size() == 2 && div.size() == 3) {
      for (int i = 0; i < div.size(); i++) printf("%d ", div[i]);
      puts("\n1");
    } else {
      vector<int> now;
      for (int i = 0; i < prime.size(); i++) {
        int d1 = prime[i], d2 = prime[(i + 1) % prime.size()];
        for (int j = 0; j < div.size(); j++) {
          if (!mp[div[j]] && div[j] % d1 == 0 && div[j] % d2 == 0) {
            now.push_back(div[j]);
            mp[div[j]] = 1;
            break;
          }
        }
      }
      for (int i = 0; i < prime.size(); i++) {
        for (int j = 0; j < div.size(); j++) {
          if (!mp[div[j]] && div[j] % prime[i] == 0) {
            printf("%d ", div[j]);
            mp[div[j]] = 1;
          }
        }
        printf("%d ", now[i]);
      }
      puts("\n0");
    }
  }
  return 0;
}
