Description

假设单性繁殖成立，若一头母牛，从出生起第四个年头开始，每年生一头母牛，而生出的小母牛在之后的第四年也将具有生殖能力。按此规律，第n年时有多少头母牛？

Input

输入数据中含有不多于50个整数n（1≤n≤40）。

Output

对于每个n，输出其第n年的母牛数，每个结果对应一行输出。

Sample

Input

5 6 7 8 9

Output

3
4
6
9
13

Source: qianneng