Do you know bubble sort algorithm? It's one of the most famous sorting algorithms.

The bubble sort algorithm is stable, which can be described below:



It's easy for us to find that we need swap  times in the worst case, so the total swapping count is about , where n is the length of the given sequence.

But the above result is an approximate result. As a curious student, Ramen is wondering, among all permutations of length n, what the value of the average exact swap count is?

The input contains multiple test cases.

The first line is an integer T(1 <= T <= 10000), which indicates represents the number of test cases.

Each of the next T lines contains an integer n(1 <= n <= 1e18), represents the length of the permutation.

For each test case, output the average swap count in one single line.

To avoid possible errors, if the answer is , you need to output , i.e., , where  is the minimum number that suits . 

3
1
3
1000000000000000000

0
499122178
178803651

For n=3, all the permutations and these swap count are:
* 
* 
* 
* 
* 
* 
So the answer is .