我们定义 $A$ 为一个正整数序列，如下所示：

令 $A[0] = 1, A[1] = 1$。对于正整数 $i \ge 2$，$A[i]$ 是满足以下条件的最小正整数：对于任何满足 $i - 2k \ge 0$ 的整数 $k > 0$，序列中不存在三项 $A[i - 2k], A[i - k], A[i]$ 构成等差数列，即 $A[i] - A[i - k] \neq A[i - k] - A[i - 2k]$。

该序列由以下方式唯一确定：$A[0] = 1, A[1] = 1, A[2] = 2, A[3] = 1, A[4] = 1, A[5] = 2, A[6] = 2, A[7] = 4, A[8] = 4$ 等。序列元素 $A[2]$ 不能为 $1$，因为否则 $A[0] = 1, A[1] = 1, A[2] = 1$ 将构成等差数列；此处 $i = 2$ 且 $k = 1$。如果 $A[2]$ 是大于 $1$ 的任何整数，则满足条件。因此，$A[2]$ 应为所有可能值中的最小正整数 $2$。同理，容易得出 $A[3] = 1$。序列元素 $A[4]$ 不能为 $3$，因为否则 $A[4] - A[4 - 2] = A[4 - 2] - A[4 - 2 \times 2]$；此处 $i = 4$ 且 $k = 2$。对于 $A[4]$，其他自然数如 $1, 2$ 和 $4$ 也是可能的，但最小的一个是 $1$。因此，$A[4] = 1$。

该序列被称为“田野之火”（fire on field）或“森林火灾”（forest fire），因为该序列的散点图看起来就像田野中蔓延的火势。见下图。

Fire on Field

给定一个非负整数 $n$，编写一个程序输出 $A[n]$。

输入格式

程序从标准输入读取数据。输入包含一行，含有一个非负整数 $n$ ($0 \le n \le 1,000$)。

输出格式

程序输出到标准输出。打印恰好一行，该行应包含 $A[n]$。

样例

样例输入 1

5

样例输出 1

2

样例输入 2

8

样例输出 2

4

样例输入 3

100

样例输出 3

4