Code

using namespace std;

#ifdef DEBUG
#include <fstream>
ifstream IN("input.txt");
ofstream OUT("output.txt");
#endif

#ifndef DEBUG
#include <iostream>
#define IN cin
#define OUT cout
#endif

bool prs[1000001];
pair<int, int> nxt[1000001];
bool was[1000001];
int mas[1000001];

int n;

int main() {
	ios_base::sync_with_stdio(0);
	IN >> n;
	int x;
	int max = 0;
	for (int i = 0; i < n; ++i) {
		IN >> mas[i];
		if (mas[i] > max) max = mas[i];
	}
	for (int i = 2; i <= max; i++) {
		if (!was[i]) {
			was[i] = true;
			prs[i] = true;
			int k = 2 * i;
			int j = 2;
			for (; k <= max; k += i, ++j) {
				if (!was[k]) nxt[k] = { i, j };
				was[k] = true;
				prs[k] = false;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (prs[mas[i]]) OUT << mas[i];
		else {
			int x = mas[i];
			while (!prs[x]) {
				OUT << nxt[x].first << " ";
				x = nxt[x].second;
			}
			if (x > 1) {
				OUT << x;
			}
		}
		OUT << endl;
	}
}