Problem Description

Koishi has decided to step out of the fantasy realm and become a master of mathematics!

Flandre heard that she is good at math and gave Koishi a construction problem:

Task1: Determine whether it is possible to construct a permutation of length \( n \) consisting of numbers \( 1 \dots n \) such that the \( n \) prefix sums are all distinct under modulo \( n \).

Task2: Determine whether it is possible to construct a permutation of length \( n \) consisting of numbers \( 1 \dots n \) such that the \( n \) prefix products are all distinct under modulo \( n \).

Following the usual routine, Koishi pretends she doesn't know how to solve it and comes to you for help.

Input Format

The first line contains two integers \( X \) and \( T \), representing the task type and the number of test cases within the test point, respectively.

The next \( T \) lines each contain a single integer representing \( n \) in each test case.

Output Format

To facilitate the writing of the Special Judge (SPJ), you need to follow the output format strictly.

For each test case, output a single line:

1. If you believe there is no valid construction for the current data, output a single integer \( 0 \).
2. If you believe there is a valid construction for the current data but you cannot construct it, output a single integer \( 1 \).
3. If you believe there is a valid construction for the current data and you have successfully constructed it, output an integer \( 2 \) followed by \( n \) integers representing the construction.

Each pair of integers should be separated by a space.

Sample Input and Output

Sample Input #1

1 1
8

Sample Output #1

2 8 7 6 5 4 3 2 1

Sample Input #2

2 1
11

Sample Output #2

2 1 2 3 5 10 6 7 4 9 8 11

Notes

For each test case:

1. If your judgment on the existence of the construction is correct, you will earn \( 30\% \) of the points. If your construction is valid or it is indeed impossible to construct, you will earn the remaining \( 70\% \) of the points.
2. If your judgment on the existence of the construction is incorrect, you will not earn any points.

For each test point, your score will be the minimum score among all data points within the test case.

Test Point Type 1: \( 10 \) points, where \( X = 1 \) and \( 1 \leq n \leq 10 \).
Test Point Type 2: \( 40 \) points, where \( X = 1 \) and \( 1 \leq n \leq 10^5 \).
Test Point Type 3: \( 10 \) points, where \( X = 2 \) and \( 1 \leq n \leq 10 \).
Test Point Type 4: \( 40 \) points, where \( X = 2 \) and \( 1 \leq n \leq 10^5 \).

For all test points, \( 1 \leq T \leq 10 \).

见题面 Input 部分

见题面 Output 部分