今天是Tabris和mengxiang000来到幼儿园的第3天，mengxiang000接到了一个布置会场的任务。
他需要将贵宾观众席的椅子排成一排，一共需要N个。
幼儿园只有两种椅子，所以他也只能使用两种椅子。（A类型和B类型）并且假设每种椅子的数量都是无限的。
而其如果想要摆置一个B类型的椅子，对应就需要必须有连续两个一起布置。换句话说，就是如果出现了B类型的椅子，其必须且只有两个连着B类型的椅子。
mengxiang000突然想知道对应N个椅子排成一列，他能够有多少种布置的方式.
本题包含多组输入第一行输入一个整数t，表示测试数据的组数
每组测试数据包含一行，输入一个整数N，表示一共需要摆放的椅子数量
t<=30
1<=N<=30
每组测试数据输出包含一行，表示一共有多少种布置的方式。