阿牛想在一块牛肉干上刻下一个长度为 n 的字符串，字符串只允许包含字符 E、O、F 三种（可以只使用其中一种或两种，但必须只由这三种字符组成）。同时，阿牛禁止在串中出现两个相邻的 O（即子串 "OO" 不允许出现）。

请你帮助阿牛计算：对于给定的长度 n ，一共有多少种不同的字符串满足上述条件？

输入包含多个测试实例，每个测试实例占一行，每行包含一个整数 n （ 0 < n < 40 ）。
输入直到文件末尾（EOF）结束。

对于每个测试实例，输出一行，包含一个整数，表示满足条件的字符串总数。

样例说明

• 当 ( n = 1 ) 时，可选的字符有 E、O、F，共 3 种。
• 当 ( n = 2 ) 时，总共有 ( 3 \times 3 = 9 ) 种组合，但其中 "OO" 不合法，因此合法数为 8。

数据范围与约定

• 0 < n < 40
• 输入包含多组数据，直到 EOF。