芜湖，马上六一儿童节了，同学们兴致都很高，打算在学校举行一个活动，好了，任务来了，你需要将当天活动的板凳摆成一排，一共需要n个。
学校只有A、B两类凳子，（A、B凳子数量无限）并且B凳子还有点毛病，它需要和自己同类的另一个凳子拼在一起才能使用，也就是说，如果有B板凳，则必然是成双成对的挨在一起。
突然啊，有人问你，把这n个凳子排成一排，一共有多少种布置的方式。

本题包含多组输入第一行输入一个整数t，表示测试数据的组数
每组测试数据包含一行，输入一个整数n，表示一共需要摆放的椅子数量
t<=30
1<=n<=30

每组测试数据输出包含一行，表示一共有多少种布置的方式。

第一个样例，AA，BB两种方案。
第二个样例，AAAA,BBBB,AABB,ABBA,BBAA五种方案  对于ABBB 因为有连续3个B类型椅子所以不可行

2021级ACM集训队选拔赛（6）