#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define N 1000*1000
vector <int> prime;
bool mark[2*N];
void erat()
{
	for(int i=2;i<=N;i++)
		if(!mark[i])
		{
			prime.push_back(i);
			for(int j=2*i;j<=N;j+=i)
				mark[j]=true;
		}
 
}
 
int main()
{ 
    erat();
    for(int i=0;i<100;i++)
    {
    	int n,ans=1000*1000;
    	cin>>n;
    	for(int j=0;j<prime.size();j++)
    		ans=min(ans,abs(n-prime[j]));
    	cout<<ans<<endl;	
 
    }
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIE4gMTAwMCoxMDAwCnZlY3RvciA8aW50PiBwcmltZTsKYm9vbCBtYXJrWzIqTl07CnZvaWQgZXJhdCgpCnsKCWZvcihpbnQgaT0yO2k8PU47aSsrKQoJCWlmKCFtYXJrW2ldKQoJCXsKCQkJcHJpbWUucHVzaF9iYWNrKGkpOwoJCQlmb3IoaW50IGo9MippO2o8PU47ais9aSkKCQkJCW1hcmtbal09dHJ1ZTsKCQl9CiAKfQogCmludCBtYWluKCkKeyAKICAgIGVyYXQoKTsKICAgIGZvcihpbnQgaT0wO2k8MTAwO2krKykKICAgIHsKICAgIAlpbnQgbixhbnM9MTAwMCoxMDAwOwogICAgCWNpbj4+bjsKICAgIAlmb3IoaW50IGo9MDtqPHByaW1lLnNpemUoKTtqKyspCiAgICAJCWFucz1taW4oYW5zLGFicyhuLXByaW1lW2pdKSk7CiAgICAJY291dDw8YW5zPDxlbmRsOwkKIAogICAgfQogICAgcmV0dXJuIDA7Cn0=

MTAgMjAgMzAgMTIxIDM0MzIxIDUyMiAx

10 20 30 121 34321 522 1