Neko猫是一个非常喜欢玩数字游戏的会说话的肥猫，常常会想到非常多非常好玩的数字游戏。有一天，它想到一个叫做素数间隙的游戏。据Neko猫的定义，素数间隙是两个相邻素数p和q组成的开区间[p, q)。所以素数间隙的长度就是q-p。

比如7和11在素数表里是两个相邻的素数。所以7和11的素数间隙的长度为11-7，为4。

如今Neko猫会给你非常多个正整数K（1＜K≤1299710），让你能立马求出包括数字K的素数间隙的长度。

为方便起见。假设K是素数，则输出0。

输入包括T组数据（1≤T≤1000）。每组測试数据占一行。是一个正整数K（1＜K≤1299710）。

输出T行，每行一个非负数。这个非负数是包括输入数字K的素数间隙的长度。不应有其它字符出如今输出中。

10

11

27

2

492170

4

0

6

0

114

水一发睡觉。。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <string>

#include <cctype>

#include <vector>

#include <cstdio>

#include <cmath>

#include <deque>

#include <stack>

#include <map>

#include <set>

#define ll long long

#define maxn 1299730

#define pp pair<int,int>

#define INF 0x3f3f3f3f

#define max(x,y) ( ((x) > (y)) ? (x) : (y) )

#define min(x,y) ( ((x) > (y)) ? (y) : (x) )

using namespace std;

int pri[maxn],n;

void init()

{

	memset(pri,1,sizeof(pri));

	pri[1]=0;

	for(int i=2;i<maxn;i++)

	{

		if(pri[i])

		{

			for(int j=2;j*i<maxn;j++)

				pri[i*j]=0;

		}

	}

}

int main()

{

	init();

	while(~scanf("%d",&n))

	{

		if(pri[n])

		{

			puts("0");

			continue;

		}

		int l=n,r=n;

		while(!pri[--l]);

		while(!pri[++r]);

		printf("%d\n",r-l);

	}

	return 0;

}