# [Solution] Permutation GCD solution codechef

Permutation GCD solution codechef – Chef is interested in the sum of GCDs of all prefixes of a permutation of the integers \{1, 2, \ldots, N\}.

## [Solution] Permutation GCD solution codechef

Formally, for a permutation P = [P_1, P_2, \ldots, P_N] of \{1, 2, \ldots, N\}, let us define a function F_i = \gcd(A_1, A_2, A_3, \ldots, A_i). Chef is interested in the value of F_1 + F_2 + \ldots + F_N.

Now, Chef wants to find a permutation of \{1, 2, \ldots, N\} which has the given sum equal to X. Please help Chef find one such permutation. In case there is no such permutation, print -1. In case of multiple answers, any of them will be accepted.

A permutation of \{1, 2, \ldots, N\} is a sequence of numbers from 1 to N in which each number occurs exactly once.

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of a single line containing two space separated integers N and X denoting the length of required permutation and the required sum of GCDs of all prefixes respectively.

### Output Format

• If there is a valid permutation that satisfies the required condition, then:
• In a single line, output N space-separated integers denoting the required permutation permutation.
• If there is no permutation, print -1 in a single line.

## Permutation GCD solution codechef

• 1 \leq T \leq 10^4
• 1 \leq N \leq 1000
• 1 \leq X \leq 2\cdot N – 1
• The sum of N over all test cases won’t exceed 3\cdot 10^5.

### Sample 1:

Input

Output

4
1 1
2 1
4 6
3 5

1
-1
2 4 3 1
3 2 1


## Permutation GCD solution codechef Explanation:

Test case 1: The only possible permutation has a sum of 1, as required.

Test case 2: The two permutations of length 2 are:

• [1, 2] with a value of 1 + 1 = 2
• [2, 1] with a value of 2 + 1 = 3

None of them have a sum of X = 1, so we output -1.

Test case 3: For P = [2, 4, 3, 1], we have:

• F_1 = 2
• F_2 = \gcd(2, 4) = 2
• F_3 = \gcd(2, 4, 3) = 1
• F_4 = \gcd(2, 4, 3, 1) = 1

The sum of these values is 6, as required.