In the first year when new comers arrived in IITB, they were randomly alloted rooms by the hall manager of hostel-5 based on availability of rooms and the timings of arrivals of the students. This allocation resulted in all the 'N' students of CSE being alloted a single wing and everyone was happy. However after some days all the students had compatibility issues with their neighbours and would always end up quarreling over petty issues with their neighbours. Everyone in room 'i' except room number '1' and room number 'N' had 2 neighbours i.e. room number 'i-1' and room number 'i+1'. Both room number 'N' and room number '1' had one neighbour and everyone quarrels with their neigbours ONLY and no one else.So all of them decided that when some or all of them (yes, they had the option of retaining rooms in the older hostels as well :)) would shift to hostel-14 the next year, they would request the hall manager to be alloted rooms such that none of the current neighbours would get rooms adjacent to each other. The new hall manager, already fed up with the current allocation in the new hostels told a group of the students who approached him with the problem that he did not want any additional hassles, and being CS students they should themselves figure out ways in which some or all of them can shift to new hostel such that any random allocation by the hall manager in consecutive rooms would not result in any quarrels in the new hostel. So assuming that each of the students are labelled by the room number they were alloted in the first year, help them find the number of possible groups in which they can shift to the new hostel so that no allocation by the hall manager to consecutive rooms would result in any quarrels in the new hostel.

Input Format
The first line of input would consist of 'T' the number of test cases. Then 'T' cases would follow, each of the test case would consist of a single number 'N', the number of students.

Output Format
For each test case output a single line containing the number of possible ways in which the 'N' students can form a group so that no allocation by the hall manager to consecutive rooms would result in any quarrels in the new hostel. (For detailed explanation refer to sample output).

Constraints
1<=T<=50
1<=N<=75