Saraff is a nasty guy. He tries his best to mock poor Killjee. Today he has an evil plan to mock killjee, He has prepared a ridiculous list and ask Killjee how many distinct positive integers this list has.

To prepare a list Saraff first make all permutations of $1,2,3,___,n$.Then appends magic value of every pair of permutation into the list.

Magic value of a pair of permutation A and B is $\sum\limits_{i=1}^n |A_i - B_i|$.

Given N find number of distinct positive numbers in Saraff's list to help Killjee.

$INPUT CONSTRAINTS$

• $1 \le N \le 10^{18}$
• $1 \le T \le 10^5$

INPUT FORMAT

First line of input contains a single integer T, denoting number of test cases. T lines follow each containing a single integer N.

OUTPUT FORMAT

For each test case print number of distinct positive number Saraff's list contain.