#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>


#include "gmp.h"
#include <gmpxx.h>

using namespace std;



void pollard(mpz_t n, int c)
{
	int k = 1, l = 1;

	mpz_t g, t1, t2;
	mpz_init (g);
	mpz_init (t1);
	mpz_init (t2);

	mpz_t x, x1, P, a;
	mpz_init_set_si (a, c);
	mpz_init_set_si (x, 2);
	mpz_init_set_si (x1, 2);

	mpz_init_set_ui (P, 1);


	while(mpz_cmp_ui(n, 1) != 0)
	{
		while(true)
		{
			mpz_mul (x, x, x);
			mpz_add (x, x, a);
			mpz_mod (x, x, n);

			mpz_sub (t1, x1, x);
			mpz_mul (t2, P, t1);
			mpz_mod (P, t2, n);

			if(--k > 0) continue;

			mpz_gcd (g, P, n);
			if(mpz_cmp_ui(g, 1) != 0) break;

			mpz_set(x1, x);
			k = l;
			l *= 2;
			for(int i = 0; i < k; i++)
			{
				mpz_mul (x, x, x);
				mpz_add (x, x, a);
				mpz_mod (x, x, n);
			}
		}

		mpz_div (n, n, g);

		if (!mpz_probab_prime_p (g, 3))
		{
			while(true)
			{
				mp_limb_t randomNr;
				mpn_random (&randomNr, (mp_size_t)1);
				c = (int)randomNr;
				if(c != 2 && c != 0) break;
			}
			pollard(g, c);
		}
		else
			gmp_printf("%Zd\n", g);

		if(mpz_probab_prime_p (n, 3))
		{
			gmp_printf("%Zd\n", n);
			break;
		}
	}

	mpz_clear (g);
	mpz_clear (P);
	mpz_clear (t2);
	mpz_clear (t1);
	mpz_clear (a);
	mpz_clear (x1);
	mpz_clear (x);
}

int main (int argc, char *argv[])
{

	mpz_t tt;
	mpz_init(tt);
	while(gmp_scanf("%Zd", tt))
	{
		pollard(tt, 1);
		printf("\n");
	}


	return 0;
}