蓝白条

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

现在有一张布,上面有 n 个平行的条纹,现在你需要把这 n 个条纹分别染成白色或者蓝色。

但是有一些限制,染色的过程中不能有两个白色的条纹相邻。

例如当 n = 3 时,“蓝白蓝”,“白蓝蓝”,“蓝蓝蓝”都是合法的,但是“白白蓝”,“白白白”,“蓝白白”,这些都是不合法的。

请计算出条纹数为 n 时,合法的染色方案数。

Input

多组输入:

    每组数据输入一个 n,代表条纹的数量。(1 <= n <= 30)

Output

每组数据输出一行,为合法的染色方案数。

Sample Input

1
2
3

Sample Output

2
3
5

Hint

Source

【2017级《程序设计基础(B)II》中外期末上机考试】Fish