Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

C. Superultra's Favorite Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Superultra, a little red panda, desperately wants primogems. In his dreams, a voice tells him that he must solve the following task to obtain a lifetime supply of primogems. Help Superultra!

Construct a permutation p of length n such that pi+pi+1 is composite over all 1in1. If it's not possible, output 1.

A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

An integer x is composite if it has at least one other divisor besides 1 and x. For example, 4 is composite because 2 is a divisor.

Input

The first line contains t (1t104) — the number of test cases.

Each test case contains an integer n (2n2105) — the length of the permutation.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case, if it's not possible to construct p, output 1 on a new line. Otherwise, output n integers p1,p2,,pn on a new line.

Example
Input
2
3
8
Output
-1
1 8 7 3 6 2 4 5
Note

In the first example, it can be shown that all permutation of size 3 contain two adjacent elements whose sum is prime. For example, in the permutation [2,3,1] the sum 2+3=5 is prime.

In the second example, we can verify that the sample output is correct because 1+8, 8+7, 7+3, 3+6, 6+2, 2+4, and 4+5 are all composite. There may be other constructions that are correct.