递归复习法 描述 据说，学渣复习期末考试，要用递归复习法，即当他复习知识点A的时候，他发现理解知识点A必须先理解知识点B和知识点C，于是他先去学习知识点B和知识点C，当他复习知识点B的时候，又发现理

递归复习法

描述

据说，学渣复习期末考试，要用递归复习法，即当他复习知识点A的时候，他发现理解知识点A必须先理解知识点B和知识点C，于是他先去学习知识点B和知识点C，当他复习知识点B的时候，又发现理解知识点B必须先理解知识点D与知识点E，又得先去复习知识点D和知识点E。giE100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

现在学渣小明正在通过递归复习法复习知识点n。对任意知识点1 <= k <= n，他复习这个知识点本身需要k小时的时间。但是，小明对这些知识点非常不熟悉，以至于他对任意知识点k， 3 <= k <= n，都必须先复习知识点k - 1和k - 2才能复习知识点k；在复习知识点k - 1的时候，又得先复习知识点k - 2和k - 3才能复习知识点k - 1；以此类推……。注意，即使在复习知识点k - 1的时候他已经复习过了知识点k - 2，在复习知识点k之前他已经忘掉了知识点k - 2，因此他还是会再复习一遍知识点k - 2，并重复上述的递归过程完成新的一轮k - 2的复习后，才会复习知识点k。giE100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

现在请问他一共需要多少个小时才能完成知识点n的复习？giE100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

第一行是一个整数m，代表数据组数，1 <= m <= 25giE100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
之后m行，每行是一组数据，即一个整数n，1 <= n <= 25

输出

对每组数据，输出小明复习知识点n所需要的时间

样例输入

9
1
2
3
5
7
9
15
20
25

样例输出

1
2
6
23
71
200
3786
42164
467833

提示

第一个输入n=1，需要复习一个小时。giE100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
giE100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第二个输入n=3，此时他需要先复习知识点1和知识点2，再复习知识点3，需要复习1+2+3=6个小时。giE100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
giE100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第三个输入n=5，此时他为了复习知识点5，必须先复习知识点3与知识点4。之前已知复习知识点3需要6个小时。复习知识点4前需要再复习知识点3与知识点2，加上复习知识点4本身的时间，共需要2+6+4=12个小时。因此，复习知识点5共需要6+12+5=23小时。