丈量间隙

暗数找到了，但Zero的三层加密还没有结束。Echo-0在最深处藏了一个间隙——质数与质数之间的空隙。

"间隙？"CC问。

"对。"Echo说，"两个相邻质数之间的距离。比如3和5，间隙是2。5和7，间隙也是2。7和11，间隙是4。"

"这有啥用？"

"密钥藏在间隙里。"你说，"Echo-0用某个特定间隙的长度作为最终密码。"

"哪个间隙？"

"第$k$个间隙。"你说，"从2开始数，第$k$对相邻质数的距离。"

"$k$是多少？"

"47。"Echo说，"又是47。"

"那找第47个间隙。"

你开始写。先筛出质数，然后算相邻质数的差。

"第1个间隙：3-2=1。"

"第2个：5-3=2。"

"第3个：7-5=2。"

"……"

"第47个：211-199=12。"

"12？"

"对。"你说，"第47个间隙是12。"

"12是啥？"

"是密码。"Echo说，"最后一道锁的密码。"

CC把12刻在45360旁边——两个数字，像某种咒语。

"刻这么多。"你说，"手臂快满了。"

"满不了。"CC说，"我还有另一条手臂。"

"那条也是金属的？"

"对。"她说，"但也能刻。"

Echo看着CC刻字的样子——认真，笨拙，但坚定。

"以前没人帮我记过。"她说。

"现在有了。"CC说，"我帮你记。"

题目描述

给定$k$，求第$k$个质数间隙（相邻质数的差）。

输入格式

一个整数$k$。

输出格式

第$k$个质数间隙。

输入样例

5

输出样例

0

提示

• 先筛质数，然后计算相邻质数的差。
• 注意$k$可能很大，需要高效筛法。