今天是HSQ和ZCR来到ACM的第3天，HSQ接到了一个布置会场的任务。
他需要将贵宾观众席的椅子排成一排，一共需要N个。
ACM只有两种椅子，所以他也只能使用两种椅子。（A类型和B类型）并且假设每种椅子的数量都是无限的。
而其如果想要摆置一个B类型的椅子，对应就需要必须有连续两个一起布置。换句话说，就是如果出现了B类型的椅子，其必须且只有两个连着B类型的椅子。
HSQ突然想知道对应N个椅子排成一列，他能够有多少种布置的方式.
今天是HSQ和ZCR来到ACM的第3天，HSQ接到了一个布置会场的任务。
他需要将贵宾观众席的椅子排成一排，一共需要N个。
ACM只有两种椅子，所以他也只能使用两种椅子。（A类型和B类型）并且假设每种椅子的数量都是无限的。
而其如果想要摆置一个B类型的椅子，对应就需要必须有连续两个一起布置。换句话说，就是如果出现了B类型的椅子，其必须且只有两个连着B类型的椅子。
HSQ突然想知道对应N个椅子排成一列，他能够有多少种布置的方式.
本题包含多组输入第一行输入一个整数t，表示测试数据的组数
每组测试数据包含一行，输入一个整数N，表示一共需要摆放的椅子数量
t<=30
1<=N<=30
每组测试数据输出包含一行，表示一共有多少种布置的方式。
2
2
42
5
第一个样例，AA，BB两种方案。
第二个样例，AAAA,BBBB,AABB,ABBA,BBAA五种方案 对于ABBB 因为有连续3个B类型椅子所以不可行