MLE祝你元宵节快乐!

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一个汤圆串可由长为 1 的 "M汤圆" 和长为 2 的 “LE汤圆” 两种汤圆组成,那么要组成长度为 n 的汤圆串可以有多少种不同的方案?

Input

先输入一个整数 t (1 <= t <= 100) 表示组数。

对于每组数据,输入一个整数 n (0 <= n <= 90),表示汤圆串的长度。

Output

对于每组输入,输出一个整数代表答案。

Sample Input

2
1
2

Sample Output

1
2

Hint

Source

【2017年寒假集训 阶段测试赛2 - 元宵节专场】MLE_kenan