508001 - 不相邻取数游戏

【例题描述】不相邻取数游戏（choice）

自然数1至N，按顺序排成一排，你可以从中取走任意个数字，但是相邻的两个不可以同时被取走。请问一共有多少种取法？

第一行为一个整数T，表示有T组数据，随后T行，每行一个整数N（1＜N＜50）

输出T行，每行一个答案。