private List<Long> brute(long n) {
		List<Long> res = new ArrayList<Long>();
		for (long i = 2; i * i <= n; ++i) {
			while (n % i == 0) {
				res.add(i);
				n /= i;
			}
		}
		if (n > 1) {
			res.add(n);
		}
		return res;
	}
	Random rm = new Random(31);

	private List<Long> solve(long n) {
		if (n < 100) {
			return brute((int) n);
		}
		List<Long> res = new ArrayList<Long>();
		if (n != 1) {
			if (BigInteger.valueOf(n).isProbablePrime(100)) {
				res.add(n);
			} else {
				long x = Math.abs(rm.nextInt()) % n;
				long y = x;
				while (true) {
					x = f(x, n);
					y = f(f(y, n), n);
					long diff = Math.abs(x - y);
					long divider = gcd(diff, n);
					if (divider == 1) {
						continue;
					} else if (divider == n) {
						x = Math.abs(rm.nextInt()) % n;
						y = x;
					} else {
						res.addAll(solve(n / divider));
						res.addAll(solve(divider));
						break;
					}
				}
				Collections.sort(res);
			}
		}
		return res;
	}

	private long gcd(long a, long b) {
		while (b != 0) {
			long tmp = a % b;
			a = b;
			b = tmp;
		}
		return a;
	}

	private long f(long x, long n) {
		return (multiply(x, x, n) + 7) % n;
	}

	private long multiply(long a, long b, long MOD) {
		long res = 0;
		while (b > 0) {
			if ((b & 1) != 0) {
				res += a;
				if (res >= MOD) {
					res -= MOD;
				}
			}
			b >>= 1;
			a += a;
			if (a >= MOD) {
				a -= MOD;
			}
		}
		return res;
	}