Permutation Lock

Manao is designing a new lock mechanism for a safe.
The lock consists of a row of $N$ numbered buttons labeled from $1$ to $N$ .
To make the lock as difficult to guess as possible, Manao wants to arrange the buttons so that adjacent buttons differ as much as possible.

More precisely, consider a permutation of the integers $1$ to $N$ .
Let $D = min_{1 \leq i < N - 1} ∣ p_{i} - p_{i + 1} ∣$ be the minimum absolute difference between any two adjacent elements of the permutation.
Manao wants to choose a permutation that maximizes this value $D$ over all possible permutations of ${1, 2, \dots, N}$ .

Your task is to output any such optimal permutation.

Input Format

The first line contains a single integer $T$ — the number of test cases.
Each of the next $T$ lines contains a single integer $N$ ( $2 \leq N \leq 100$ ).

Output Format

For each test case $i$ ( $1 \leq i \leq T$ ), output Case #i: K, where $K$ is the largest possible minimum difference between adjacent elements in a permutation of ${1, \dots, N}$ . On the next line, output the corresponding permutation.

Example

Input

2
3
4

Output

Case #1: 1
2 1 3
Case #2: 2
3 1 4 2