#P1347. 武功秘籍修炼天数计算

武功秘籍修炼天数计算

题目描述

Alice 和同班同学们去悬崖边露营,却被拥有“读心术”的同学Bob 推下悬崖!令人意外的是,Alice 竟然奇迹般生还,掉进了悬崖下的热带雨林。在那里,他遇到了隐藏在山林中的大师,获得了一本共有40层的武功秘籍。

秘籍的修炼规则如下:

  • 练成第1层需要1天
  • 练成第2层需要2天
  • 练成第 nn 层(n3n \geq 3)需要的天数是前两层所需天数的和(即第 nn 层天数 = 第 n1n-1 层天数 + 第 n2n-2 层天数)

当 Alice 练成第 nn 层的当天,他会去感谢大师,庆祝直到很晚,因此只能在第二天离开

请你帮他计算,从开始修炼到离开一共需要多少天。若 n=0n=0,表示他不需要修炼,直接离开,输出0。

输入格式

第一行输入一个整数 TT (1T10000)(1 \leq T \leq 10000),代表测试组数。 接下来 TT 行,每行包含一个整数 nn (0n40)(0 \leq n \leq 40)

输出格式

对每组测试数据,输出 Alice 第几天才能离开。 (当 n=0n=0 时输出0)

样例

3
1
2
0
2
4
0

提示

题目维护者:智科23-2 张宸维 (2025.7.15) 更新为已知 TT 的多测,请勿使用重测整题。