1. 
/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Math: Primes
* Problem: 11099 - NextSameFactored
* Accepted: 2.588
* @author Evgeni Pavlidis
*
*/
import java.io.*;
import java.util.*;

class Main {

// debugging
private static boolean DEBUG = false;
private static Stack<Integer> stack = new Stack<Integer>();


private static final int MAX = 1000000;
private static final int LIMIT = 2000000;
private static boolean[] isPrime = new boolean[MAX+1];
// saves the prime factors for [x][...]
private static int[][] factors = new int[MAX+1][7];
// saves the number of prime factors for [x]
private static int[] index = new int[MAX+1];

// saves the minimum next number found so far
private static long min;


private static void sievePrimes()
{
isPrime[2] = true;
factors[2][index[2]++] = 2;
for(int j = 4; j <= MAX; j+=2)
factors[j][index[j]++] = 2;

for(int i = 3; i <= MAX; i+=2)
isPrime[i] = true;

int root = (int)Math.sqrt(MAX);
for(int i = 3; i <= root; i+=2)
if(isPrime[i])
for(int j = i+i; j <= MAX; j+=i)
{
isPrime[j] = false;
factors[j][index[j]++] = i;
}
}

private static void findNext(int n, long current)
{
if(current > min || current >= LIMIT)
return;

if(current > n)
min = current;

// go through all prime factors
for(int i = 0; i < index[n]; i++)
{
current = current * factors[n][i];

if(DEBUG)
{
stack.push(factors[n][i]);
System.out.println(stack + " ==> " + current);
}

findNext(n, current);
current = current / factors[n][i];

if(DEBUG)
stack.pop();
}
}

private static long getNextPrime(int n)
{
long base = 1;
long next;

// tests if n contains a prime that wasn't sieved
int test = n;

for(int i = 0; i < index[n]; i++)
{
while( test % factors[n][i] == 0 )
test /= factors[n][i];

base *= factors[n][i];
}

if(test != 1)
{
factors[n][index[n]++] = test;
base *= test;
}

if(DEBUG)
{
System.out.println("Factors: " + Arrays.toString(factors[n]));
stack.clear();
}

min = n*factors[n][0];

findNext(n, base);

return min;
}

public static void main(String...args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String input;
int n;
long next;

sievePrimes();

while( (input = reader.readLine()) != null )
{
n = Integer.parseInt(input);

// special case
if(n == 1)
{
System.out.println("Not Exist!");
continue;
}

if(isPrime[n])
next = (long)n*n;
else
next = getNextPrime(n);

if(next > LIMIT)
System.out.println("Not Exist!");
else
System.out.println(next);
}
}
}