Description

Daimin big cow 平时喜欢研究一些比较深奥的问题，最近他碰到了一个难题，所以就向你们求救了。问题的描述是这样的：

某人在年初买了一头刚生下的母牛，3年后的年初，小母牛生下了一头小母牛。4年后的年初，小母牛生下了一头小公牛。假设以后每年年初，该小母牛一年下母牛，一年下公牛。而所有的小母牛都按照这种方式进行生产。问你n年以后将会有多少头母牛。

Input

输入数据包含多组，每组有一个整数n（0<=n<=100）。

Output

对于每组输入，输出当年一共有多少头母牛。

Sample

Input

1
2
3

Output

1
1
2

Source: t_c