素数间隙

Time Limit: 1000 ms Memory Limit: 262144 KiB

Problem Description

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

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

现在Neko猫会给你很多个正整数K1K1299710),让你能立刻求出包含数字K的素数间隙的长度。为方便起见,如果K是素数,则输出0

Input

 

输入包含T组数据(1T1000),每组测试数据占一行,是一个正整数K1K1299710)。

Output

 

输出T行,每行一个非负数,这个非负数是包含输入数字K的素数间隙的长度,不应有其他字符出现在输出中。

Sample Input

10
11
27
2
492170

Sample Output

4
0
6
0
114

Hint

  

Source

青岛理工交流赛