Fake GCD Solution Codechef september cook off 2021

Fake GCD Solution Codechef september cook off 2021

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.


  • 1T5001≤T≤500
  • 2N5002≤N≤500

Sample Input 1 


Sample Output 1 

3 4 1 2


  • 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: Click here

Leave a Comment