题目描述

徐老师有一个特殊的序列 $a_0,a_1,a_2,a_3 \dots a_n$

这个序列满足两条规则：

1. $a_0 = a_1 = 1$ 且 $a_i > 0$
2. 对于任意整数 $i$ 和 $k(k > 0, i - 2 * k \geq 0)$ 满足 $a_i - a_{i-k} \not= a_{i-k} - a_{i-2 * k}$

现在徐老师准备从依次生成满足条件的 $a_2,a_3,a_4 \dots a_n$

对于徐老师正准备生成的数字 $a_i$ 来说，如果存在多个满足条件的数字，徐老师会选择最小的那个

现在徐老师想知道，他最终生成的序列中，$a_n$ 的值会是多少？

输入格式

输入一个整数 $n$ 表示要生成的序列长度

输出格式

输出一个整数表示 $a_n$ 的值

数据范围

对于 $30\%$ 的数据满足 $1 \leq n \leq 100$

对于 $60\%$ 的数据满足 $1 \leq n \leq 1000$

对于 $100\%$ 的数据满足 $1 \leq n \leq 2000$

样例输入1

5

样例输出1

2

样例输入1

8

样例输出1

4