阿牛想在一块牛肉干上刻下一个长度为 $ 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。