package extra; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; public class P1498 { static Scanner in; static PrintWriter out; static String INPUT = ""; static void solve() { final int n = 100002; List> lists = new ArrayList<>(); for(int i = 0;i < n;i++)lists.add(new ArrayList<>()); long[] val = new long[n]; for(int i = 1;i < n;i++){ val[i] = (long)i*i+1; } for(int i = 1;i < n;i++){ if(val[i] == 1)continue; long p = val[i]; for(long j = i;j < n;j+=p){ int jj = (int)j; while(val[jj] % p == 0){ val[jj] /= p; lists.get(jj).add(p); } } } for(int Q = ni();Q > 0;Q--){ List f = lists.get(ni()); for(long v : f){ out.print(v + " "); } out.println(); } } public static void main(String[] args) throws Exception { in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT); out = new PrintWriter(System.out); solve(); out.flush(); } static int ni() { return Integer.parseInt(in.next()); } static long nl() { return Long.parseLong(in.next()); } static double nd() { return Double.parseDouble(in.next()); } static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }