#79. [WPXCO 1.5 AUG] [动态规划] Determine O

内存限制:256 MiB 时间限制:1000 ms 输入文件:determine.in 输出文件:determine.out
题目类型:传统 评测方式:文本比较
上传者: 2024-J-W010

题目描述

Kirole 定义,一个字符串 是 “EOF 的” 当且仅当这个字符串满足如下两个条件:

  • 只由 “E、O、F” 三个字母组成。
  • 相邻两个字符不能为 “O”。

给定阈值 ,Kirole 想知道有多少个长度为 的字符串是 “EOF 的”。

输入格式

第一行一个正整数 表示数据组数。

接下来 行,每行一个正整数 表示字符串的长度。

输出格式

行,每行一个正整数,表示 “EOF 的” 字符串的个数 的结果。

样例

样例

样例输入

2
2
3

样例输出

8
22

样例解释

对于第一个 ,是 “EOF 的” 字符串有:

  • EE、EO、EF
  • OE、OF
  • FE、FO、FF

数据范围与提示

对于 的数据,保证

对于 的数据,保证

对于 的数据,保证