说明

有一只青蛙，叫作妙妙蛙。妙妙蛙的家在河边，河底有一条楼梯通往它家，已知楼梯共有40级，但是由于河的水位会随着天气的不同而涨高或者降低，妙妙蛙每次回家需要跳的楼梯长度都不一样（因为可以游到河面然后再跳）。已知妙妙蛙每次能够跳1级或者2级楼梯，妙妙蛙想知道它回家有多少种不同跳法。帮帮它吧~

输入格式

第一行输入一个整数T,表示样例数。接下来的第二行到第T+1行，每行一个数字d（0<=d<=40)，表示某一天的水位高度。

输出格式

每组样例一个输出，表示不同的方法数。

样例

1
38

2

提示

当水位高度为38的时候，妙妙蛙只需要跳两级楼梯，因此它有2种方法：跳1级，到达39级，再跳1级，到达40级。跳2级，到达40级。