该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

打铁还需自身硬（咣！）

百度之星程序设计大赛（亦称百度之星·程序设计大赛）由百度在线网络技术（北京）有限公司（简称百度公司）举办，是一项旨在展示学生创新能力和编写程序、分析、解决问题能力的年度竞赛，从 2005 年至今已成功举办了 19 届，累计参赛选手三十余万名，覆盖数千所院校，成为中国最具知名度、最有影响力的程序设计大赛之一，大量优秀人才通过大赛脱颖而出，被誉为国内程序员的“黄埔军校”和“造星工厂”。大赛已入选中国高等教育学会“全国普通高校大学生竞赛排行榜”竞赛项目榜单。百度之星是百度 500 万大模型人才培养计划的组成部分，长期致力于搭建一个以赛促教、以赛促学的程序设计和人工智能人才培养平台，推动中国互联网和 AI 领域人才成长。

——以上内容来自百度之星官网。

百度之星有点难的（好吧超级难），反正教练的意思是这个比赛是为了给百度筛选竞赛人才的。它自然会更有含金量一点（毕竟其他比赛也不发铁牌这种东西百度之星还要专门发个鼓励一下是不）

百度之星是个人 ACM 赛制。C++赛道仅允许使用 DevC++作为 IDE。并且不允许携带纸质材料。初赛在线上举行，决赛在北京线下。

题目描述

小鹿刚打的百度之星铁牌丢在了路上，现在他需要去拿，这条路的结构如图所示。

小鹿只能走向右侧的格子，不能反向行走，例如小鹿如果从 $3$ 号格子出发，只能走向 $4$ 号格子或者 $5$ 号格子：小鹿如果从 $4$ 号格子出发，只能走向 $5$ 号格子或者 $6$ 号格子。现在假设小鹿在 $1$ 号格子，请计算他走到第 $n$ 号格子的可能路线数。

输入格式

本题有多组数据，输入共 $t+1$ 行。 第一行输入一个数字 $t (t \leq 27)$，代表数字组数。 接下来 $t$ 行，每一行输入一个整数 $n(4 \leq n \leq 30)$ 表示目标格子。

输出格式

输出共一行，表示从 $1$ 走到 $n$ 的路线数。

样例

2
5
7

5
13