A positive integer m is said to a pure number if and only if m can be expressed as q-th power of a prime p (q >= 1). 
Here your job is easy, for a given positive integer k, find the k-th pure number. 
 

输入格式

The input consists of multiple test cases. For each test case, it contains a positive integer k (k<5,000,000). Process to end of file.

输出格式

For each test case, output the k-th pure number in a single line. If the answer is larger than 5,000,000, just output -1.

样例输入

1
100
400000

样例输出

2
419
-1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int num[5000007];
int res[350000];
int main(){
	int i,j,sum=0,k;
	long long n;
	memset(num,0,sizeof(num));
	for(i=2;i<5000000;i++){
		if(num[i]==0){
			num[i]=1;
			res[sum]=i;
			sum++;
			n=i*i;
			for(j=i+i;j<5000000;j=j+i){
				num[j]=1;
				if(j==n){
					res[sum]=j;
					sum++;
					n=n*i;
				}
			}
		}
	}
	//printf("%d\n",sum);
	sort(res,res+sum);
	while(~scanf("%d",&k)){
		if(k<=348940)
		printf("%d\n",res[k-1]);
		else
		printf("-1\n");
	}
	return 0;
}