### Fake GCD: FAKEGCD

You are given an integer NN. Output a permutation of values from 11 to NN that satisfies the following condition:

• gcd([1+A1,2+A2,3+A3,…,N+AN])>1gcd([1+A1,2+A2,3+A3,…,N+AN])>1

It can be proven that a solution always exists. If there are multiple permutations that can satisfy the condition, then output any one of them.

As a reminder,

• A permutation of values from 11 to NN is an array containing integers from 11 to NN in any order but each of them appearing exactly once.
• GCD stands for Greatest Common Divisor. The greatest common divisor of a sequence is the largest integer dd such that all the numbers in sequence are divisible by dd. For more information, refer to here.

### Input Format

• The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
• The first line of each test case contains an integer NN.

### Output Format

For each test case, output on one line a permutation of values from 11 to NN which satisfies the above condition.

### Constraints

• 1≤T≤5001≤T≤500
• 2≤N≤5002≤N≤500

### Sample Input 1

``````1
4
``````

### Sample Output 1

``````3 4 1 2
``````

### Explanation

• For the first test case, gcd([1+3,2+4,3+1,4+2])=gcd([4,6,4,6])=2gcd([1+3,2+4,3+1,4+2])=gcd([4,6,4,6])=2 which is greater than 11, so the given permutation satisfies the condition.

Solution:

``````#include<bits/stdc++.h>
using namespace std ;

#define ll              long long
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll>
#define pii             pair<int,int>
#define ld              long double

const int M = 1000000007;
const int MM = 998244353;

template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }

#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2351
#endif

long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l,int r,char end){
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
string readStringLn(int l,int r){
}
string readStringSp(int l,int r){
}

//RNG based on mersenne_twister
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int _runtimeTerror_()
{
int N;
vector<int> odd, even;
for(int i=1;i<=N;++i) {
if(i % 2 == 1) {
odd.push_back(i);
}
else {
even.push_back(i);
}
}
shuffle(all(odd),rng);
shuffle(all(even),rng);
for(int i=1;i<=N;++i) {
if(i % 2 == 1) {
cout << odd.back() << "\n";
odd.pop_back();
}
else {
cout << even.back() << "\n";
even.pop_back();
}
}
return 0;
}

int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initialize();
#endif
int TESTS = 1;
//cin >> TESTS;
while(TESTS--)
_runtimeTerror_();
assert(getchar() == -1);
return 0;
}``````

* The material and content uploaded on this website are for general information and reference purposes only. Please do it by your own first.

### Correct Slippers: CORRSLP