题目描述

在$1997/1998$年西南欧区域赛（在乌尔姆举行）之后，举办了一场盛大的派对。组织团队设计了一种特殊的方式来选择需要帮忙洗碗的参赛者。参赛者排成一队，一个接一个。每个参赛者被分配一个从$2$开始的数字，第一个参赛者是$2$，第二个是$3$，第三个是$4$，依此类推。

队列中的第一个参赛者被问及他的数字（即$2$）。他被免除洗碗任务，可以继续派对，但他后面的每第二个参赛者必须去厨房（即数字为$4$、$6$、$8$等的参赛者）。接着，剩下的队列中的下一个参赛者需要报出他的数字。他回答$3$并被免除任务，但他后面的每第三个参赛者需要帮忙（即数字为$9$、$15$、$21$等的参赛者）。剩下的队列中的下一个参赛者数字为$5$并被免除任务，但他后面的每第五个参赛者被选中（即数字为$19$、$35$、$49$等的参赛者）。下一个参赛者数字为$7$并被免除任务，但他后面的每第七个参赛者需要帮忙，以此类推。

我们将那些不需要帮忙洗碗的参赛者的数字称为幸运数字。按照这个选择方案，幸运数字的有序序列为$2$, $3$, $5$, $7$, $11$, $13$, $17$等。请找出幸运数字，为下一次派对做准备。

输入格式

输入包含多个测试用例。每个测试用例包含一个整数 $n$。可以假设 $1 \leq n \leq 3000$。最后一个测试用例的输入为$0$。

输出格式

对于每个测试用例 $n$，输出一行，表示第 $n$ 个幸运数字。

输入样例 1

1
2
10
20
0

输出样例 1

2
3
29
83

来源

乌尔姆$2003$年地区赛（试题来源）