Palak likes to sort the numbers in decreasing order. But Subham and Palak are totally opposite. So, Subham wants to rearrange the numbers (already in decreasing order) in increasing order. However, Palak imposes a restriction on the way to sort these numbers in increasing order. Subham is allowed to exchange any pair of numbers that have exactly one number between them. He needs your help to sort the numbers with minimum number of exchanges and then print the number of exchanges. There might be some cases where it is not possible to bring the numbers in increasing order using above technique. Print -1 for such cases.

Note: All the numbers are distinct.

Input

The first line contains T number of test cases.

Each test case contains an integer N - total number of integers to be sorted.

Output

Output T lines containing the required number of exchanges. Output -1, if it is not possible to sort the numbers for a testcase.

Constraints

1 <= T <= 100

1 <= N <= 1000000

Example

Input:
4
55
123
67
8

Output:
729
3721
1089
-1