You are given a deck of N cards numbered 1 to N. Your goal is to pick up as many cards as possible, with only one requirement: You are not allowed to pick up a card, if it would lead to a situation where you hold three cards with numbers X, Y and Z such that X+Y=Z.
You have to calculate the number of ways in which you can take the maximum number of cards. (The order in which you pick up the cards doesn't matter.)
For example, if N=3, you can't pick up all three cards (because 1+2=3), but you can pick up any two cards. There are 3 ways of selecting two out of three cards (1 and 2, 2 and 3, 3 and 1). Thus the answer for N=3 is 3.
The first line of input contains T, the number of test cases.
Each test case consists of one line containing the number, N.
For each test case, ouput a line containing the answer to the particular test case.
N fits in 32 bit integer range.