#include <bits/stdc++.h>
using namespace std;
bool vis[10005];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    memset(vis, 0, sizeof(vis));
    int n;
    scanf("%d", &n);
    vector<int> d;
    for (int i = 1; i * i <= n; i++) {
      if (n % i == 0) {
        if (i != 1) d.emplace_back(i);
        if (i != n / i) d.emplace_back(n / i);
      }
    }
    sort(d.begin(), d.end());
    vector<int> p, co;
    for (int i = 0; i < d.size(); i++) {
      bool prime = 1;
      for (int j = 0; j < i; j++) {
        if (d[i] % d[j] == 0) {
          prime = 0;
          break;
        }
      }
      if (prime)
        p.emplace_back(d[i]);
      else
        co.emplace_back(d[i]);
    }
    if (p.size() == 1) {
      for (int i = 0; i < d.size(); i++) printf("%d ", d[i]);
      printf("\n");
      printf("0\n");
    } else if (p.size() == 2) {
      int cnt = 0;
      for (int i = 0; i < co.size(); i++) {
        if (co[i] % p[0] == 0 && co[i] % p[1] == 0) {
          cnt++;
        }
      }
      if (cnt == 1) {
        printf("%d ", p[0]);
        for (int i = 0; i < co.size(); i++) {
          if (co[i] % p[0] == 0 && co[i] % p[1] == 0) continue;
          if (co[i] % p[0] == 0) printf("%d ", co[i]);
        }
        for (int i = 0; i < co.size(); i++) {
          if (co[i] % p[0] == 0 && co[i] % p[1] == 0) printf("%d ", co[i]);
        }
        printf("%d ", p[1]);
        for (int i = 0; i < co.size(); i++) {
          if (co[i] % p[0] == 0 && co[i] % p[1] == 0) continue;
          if (co[i] % p[1] == 0) printf("%d ", co[i]);
        }
        printf("\n");
        printf("1\n");
      } else {
        printf("%d ", p[0]);
        for (int i = 0; i < co.size(); i++) {
          if (vis[i]) continue;
          if (co[i] % p[0] == 0 && co[i] % p[1] == 0) continue;
          if (co[i] % p[0] == 0) printf("%d ", co[i]), vis[i] = 1;
        }
        for (int i = 0; i < co.size(); i++) {
          if (vis[i]) continue;
          if (co[i] % p[0] == 0 && co[i] % p[1] == 0) {
            printf("%d ", co[i]);
            vis[i] = 1;
            break;
          }
        }
        printf("%d ", p[1]);
        for (int i = 0; i < co.size(); i++) {
          if (co[i] % p[0] == 0 && co[i] % p[1] == 0) continue;
          if (co[i] % p[1] == 0) printf("%d ", co[i]), vis[i] = 1;
        }
        for (int i = 0; i < co.size(); i++) {
          if (vis[i]) continue;
          if (co[i] % p[0] == 0 && co[i] % p[1] == 0) {
            printf("%d ", co[i]);
            vis[i] = 1;
          }
        }
        printf("\n");
        printf("0\n");
      }
    } else {
      for (int i = 0; i < p.size(); i++) {
        int pv = p[(i - 1 + p.size()) % p.size()];
        int cur = p[i];
        int nt = p[(i + 1) % p.size()];
        printf("%d ", cur);
        for (int j = 0; j < co.size(); j++) {
          if (vis[j]) continue;
          if (co[j] % cur == 0 && co[j] % nt == 0) continue;
          if (co[j] % cur == 0 && co[j] % pv == 0) continue;
          if (co[j] % cur == 0) printf("%d ", co[j]), vis[j] = 1;
        }
        for (int j = 0; j < co.size(); j++) {
          if (vis[j]) continue;
          if (co[j] % cur == 0 && co[j] % nt == 0)
            printf("%d ", co[j]), vis[j] = 1;
        }
      }
      printf("\n");
      printf("0\n");
    }
  }
}
