#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int st[N],primes[N],mp[N],zxzys[N],cnt,mul[N],pos[N],l[N],pos1[N],r[N],cntt[N],w[N];
int main(){
	//puts("fuck");
	
	for(int i=2;i<=1000000;i++){
		if(st[i]==0){
			mp[i]=1;
            cnt++;
            //cout<<i<<endl;
            primes[cnt]=i;
            for(int j=1;j*i<=1000000;j++){
                st[j*i]=1;
                zxzys[j*i]=i;
            }
    }
	}

//	puts("fuck");
//	s[1].insert(1);
	for(int i=2;i<=1000000;i++){
		int i1=i;
		set<int>s;
		while(i1!=1){
			s.insert(zxzys[i1]);
			int i2=i1;
			while(i2%zxzys[i1]==0){
				i2/=zxzys[i1];
			}
			i1=i2;
		}
		w[i]=s.size();
		int zt=1;
		for(auto j:s){
			zt*=j;
		}
		mul[i]=zt;
		//if(i>30)break;
	}
		//return 0;
	//cout<<w[30]<<endl;
	//puts("fuck");
//	for(int i=1;i<=1000000;i++){
//		int zt=1;
//		for(auto j:s[i]){
//			zt*=j;
//		}
//		mul[i]=zt;
//	}
//	puts("fuck");
//	return 0;
	for(int i=2;i<=N-10;i++){
		set<int>s;
		s.insert(1);
		//cout<<i<<" "<<s1[i].size()<<endl;
		int zt=mul[i];
//		cout<<i<<" "<<zt<<" "<<mul[i]<<endl;
//		cout<<i<<endl;
		while(zt!=1){
			int cnt1=0; 
			for(auto j:s){
				//int cnt1=0;
				cnt1++;
				cntt[cnt1]=j;
				
			}
			for(int j=1;j<=cnt1;j++){
				s.insert(cntt[j]*zxzys[zt]);
			}
			int ztt=zt;
			while(ztt%zxzys[zt]==0){
				ztt/=zxzys[zt];
			}
			zt=ztt;
			
		}
		//puts("fuck"); 
	//if(i==30)cout<<s1[i].size()<<endl; 
		for(auto j:s){
//			cout<<s1[i].size()<<endl;
//			cout<<j<<endl;
			if(pos[j])l[i]=max(l[i],pos[j]);
		}
//		if(i==30){
//			cout<<l[i]<<endl;
//			return 0;
//		}
		pos[mul[i]]=i;
	} 
//	puts("fuck");
	for(int i=N-10;i>=2;i--){
		r[i]=1e9;
		set<int>s;
		s.insert(1);
		//cout<<i<<" "<<s1[i].size()<<endl;
		int zt=mul[i];
		//cout<<i<<" "<<mul[i]<<endl;
//		cout<<i<<" "<<zt<<" "<<mul[i]<<endl;
//		cout<<i<<endl;
		while(zt!=1){
			int cnt1=0; 
			for(auto j:s){
				//int cnt1=0;
				cnt1++;
				cntt[cnt1]=j;
				
			}
			for(int j=1;j<=cnt1;j++){
				s.insert(cntt[j]*zxzys[zt]);
			}
			int ztt=zt;
			while(ztt%zxzys[zt]==0){
				ztt/=zxzys[zt];
			}
			zt=ztt;
			
		}
	//	puts("fuck"); 
	//if(i==30)cout<<s2[i].size()<<endl; 
		for(auto j:s){
//			cout<<s1[i].size()<<endl;
	//		if(i==30)cout<<j<<endl;
			if(pos1[j])r[i]=min(r[i],pos1[j]);
		}
//		if(i==30){
//			cout<<l[i]<<endl;
//			return 0;
//		}
		pos1[mul[i]]=i;
	}
	cout<<r[30]<<endl;
	return 0;
}