All integer numbers are divisible by primes. If a number is divisible by more than one prime number, then it obviously has a largest prime divisor. The numbers which do not fall in this category do not have a largest prime divisor. Given a number N your job is to write a program that finds its largest prime divisor. An integer number n is divisible by another integer number m if there is an integer t such that mt=n.

Input

The input file contains at most 450 sets of inputs. Each line contains a decimal integer N. N does not have more than 14 digits. Input is terminated by a line containing a single zero. So no other line except the last line contains a zero in the input. This line need not be processed.

Output

For each line of the input produce one line of output. This line contains an integer LPD, which is the largest prime divisor of the input number N. If the input number is not divisible by more than one prime number output a -1.

Sample Input                             Output for Sample Input

2

6

100

0

Problem Setter: Shahriar Manzoor

Special Thanks: Syed Monowar Hossain

#include <stdio.h>
#include <math.h>
const int N = 10000000;
unsigned mark[(N>>5)+1];
int prime[670000], pt = 0;
int GET(int x) {
    return mark[x>>5]>>(x&31)&1;
}
void SET(int x) {
    mark[x>>5] |= 1<<(x&31);
}
void sieve() {
    register int i, j;
    int sqr = N;
    SET(0), SET(1);
    for(i = 2; i <= sqr; i++) {
        if(!GET(i)) {
            prime[pt++] = i;
            for(j = i+i; j <= N; j += i)
                SET(j);
        }
    }
}
void solve(long long n) {
    int i, cnt = 0;
    long long pre = n, ans = -1;
    for(i = 0; prime[i] <= sqrt(n) && i < pt; i++) {
        if(n%prime[i] == 0) {
            ans = prime[i];
            cnt++;
            while(n%prime[i] == 0)
                n /= prime[i];
        }
    }
    if(n != 1)
        ans = n, cnt++;
    if(cnt <= 1)
        ans = -1;
    printf("%lld\n", ans);
}
int main() {
    sieve();
    long long n;
    while(scanf("%lld", &n) == 1 && n) {
        if(n < 0)   n *= -1;
        if(n <= N && GET(n) == 0)
            puts("-1");
        else
            solve(n);
    }
    return 0;
}