#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> primes;
    for (int i = 2; i * i <= n; i++)
      if (n % i == 0) {
        primes.push_back(i);
        n /= i;
        i--;
      }
    if (n != 1) primes.push_back(n);
    set<int> st;
    vector<int> ans;
    ans.push_back(primes[0]);
    st.insert(primes[0]);
    for (int i = 1; i < primes.size(); i++) {
      int val = primes[i - 1] * primes[i];
      int siz = ans.size();
      if (st.count(val) == 0) {
        ans.push_back(val);
        st.insert(val);
      }
      if (st.count(primes[i]) == 0) {
        ans.push_back(primes[i]);
        st.insert(primes[i]);
      }
      for (int j = 0; j < siz; j++) {
        int val = primes[i] * ans[j];
        if (st.count(val) == 0) {
          ans.push_back(val);
          st.insert(val);
        }
      }
    }
    for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
    printf("\n");
    printf("%d\n", (gcd(ans.back(), ans[0]) == 1 ? 1 : 0));
  }
  return 0;
}
