You are given a positive integer X. Find the largest perfect power that is at most X. Here, a perfect power is an integer that can be represented as b^p, where b is an integer not less than 1 and p is an integer not less than 2.

Constraints

* 1 ≤ X ≤ 1000
* X is an integer.

Input

Input is given from Standard Input in the following format:


X


Output

Print the largest perfect power that is at most X.

Examples

Input

10


Output

9


Input

1


Output

1


Input

999


Output

961
#include<stdio.h>
int f(int a,int b){
int u,c=1;
for(u=0;u<b;u++)c*=a;
return c;
}
int main(){
int x,i,j,ans=1,y=0;
scanf("%d",&x);
for(i=2;i*i<=x;i++){
for(j=2;y<x;j++){
y=f(i,j);
if(y<=x&&y>ans)ans=y;
}
y=0;
}
printf("%d",ans);
return 0;

}