CF2218C.The 67th Permutation Problem

Upon arriving at school, Macaque was rather brusquely greeted by his friend, AG-88301, the latter having skived off his homework due to spending the entire night yapping to an unsuspecting stranger about his groundbreaking work on a proof of the Collatz conjecture and his $ 67 $ -th unreciprocated love interest. So, as had become customary, AG-88301, with ever decreasing levels of gratitude or appreciation, made Macaque do his homework for him. At this point, Macaque had had enough, and turned to his minions (you guys!) to solve AG-88301's homework task.

You are given an integer $ n $ . You must construct a permutation $ ^{\text{∗}} $ of length $ 3n $ such that, if you partition the permutation into $ n $ contiguous blocks with $ 3 $ elements, the sum of the medians $ ^{\text{†}} $ of these blocks is maximised.

More formally, you must construct a permutation $ p $ of length $ 3n $ such that $ \sum_{i=0}^{n-1}\operatorname{median}(a_{3i+1},a_{3i+2},a_{3i+3}) $ is maximised. If there are multiple possible $ p $ , output any.

$ ^{\text{∗}} $ 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).

$ ^{\text{†}} $ The median of an array $ b $ containing $ 3 $ elements is the $ 2 $ -nd element after $ b $ is sorted in non-decreasing order.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first and only line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 10^5 $ ).

It is guaranteed that the sum of $ 3n $ does not exceed $ 3 \cdot 10^5 $ over all test cases.

For each test case, output a permutation $ p $ such that the sum of the medians of the contiguous blocks is maximised. If there are multiple possible $ p $ , output any.

In the first test case, $ [1,3,4,2,5,6] $ is a possible answer because $ \operatorname{median}(1,3,4) + \operatorname{median}(2,5,6) = 3+5 = 8 $ , and it can be shown that $ 8 $ is the maximal possible sum of medians.

In the second test case, $ [3,1,2] $ is a possible answer because the only achievable sum of medians when $ n=1 $ is $ 2 $ .