IPSC 2006 Problem I – Ideal Matches

IPSC 2006

Problem I – Ideal Matches

At a party, N couples play the following game: In the beginning, each boy takes his girl's right hand into his left hand. Now, everybody closes their eyes and they all start to move around randomly. At a given signal, everybody reaches out with his/her free hand and catches somebody else's hand. Then everybody opens their eyes.

The game is considered a success if all players form one large cycle and a failure otherwise.

After the players became tired of the game and started to chat, Tony exclaimed: "Once I was at a party where we played the game 2N-2 times, and each time it was a success. And moreover, nobody did hold somebody else's hand more than once. (Of course, except for his partner's hand.)"

Everybody knows that Tony is a notorious jester, so nobody took his exclamation too seriously. "Nah, it's not even possible!" said one of his friends.

Help Tony prove that his story really could have happened.

Problem specification

You are given the number of couples N. The boys are numbered from 0 to N-1, the girls from N to 2N-1. The girlfriend of the boy i is the girl i+N.

We may specify the result of a given game by specifying N pairs of numbers – one for each pair of people (other than a couple) that are holding hands.

Find one possible set of 2N-2 game results such that each game is a success and, except for the couples, nobody did hold somebody else's hand more than once.

Input specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line containing a single integer N.

Output specification

For each test case output 2N-2 lines. The i-th of these lines should contain 2N space-separated integers a₀, ..., a_2N-1, where for each j the people a_2j and a_2j+1 were holding hands in the i-th game.

If there is more than one solution, you may output any one of them. If there is no solution, instead of the 2N-2 lines as specified above output a single line with the word "IMPOSSIBLE".

Example

Input:

1

2

Output:

0 1 2 3
0 3 2 1

In the example, the couples are 0-2 and 1-3. In the first game, 0-1 and 2-3 were holding hands, thereby forming a circle 0-1-3-2. In the second game, we saw the circle 0-3-1-2.