XOR 삼형제

시간 제한5초메모리 제한256 MB

요약

1부터 N까지 수 중에서 서로 다른 세 수의 XOR이 0이 되지 않는 최대 부분집합을 사전식으로 가장 작은 것으로 구합니다.

난이도: 보통10점 중 5점
유형: 완전 탐색, 비트 연산
정답자: 아직 제출이 없습니다

문제

$1$ 이상 $N$ 이하의 정수 중에서 서로 다른 수를 골라 수열을 만든다. 고른 수 가운데 서로 다른 세 수 $a$ , $b$ , $c$ 를 어떻게 잡아도 $a \oplus b \oplus c \neq 0$ 이어야 한다. 여기서 $\oplus$ 는 비트 단위 배타적 논리합(XOR)이다.

이 조건을 지키는 수열 중 길이가 가장 긴 것을 구하라.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. ( $1 \leq T \leq 100$ )

다음 $T$ 개의 줄에 정수 $N$ 이 한 줄에 하나씩 주어진다. ( $1 \leq N \leq 20$ )

출력

테스트 케이스마다 두 줄에 걸쳐 답을 출력한다.

첫 줄에는 수열의 길이를 출력한다.
둘째 줄에는 수열을 오름차순으로 정렬해 공백으로 구분하여 출력한다.

길이가 가장 긴 수열이 여러 개면, 오름차순으로 정렬한 결과가 사전순으로 가장 앞서는 것 하나만 출력한다.

예제2

예제 1
입력
```
2
2
3
```
예상 출력
```
2
1 2
2
1 2
```
예제 2
입력
```
1
1
```
예상 출력
```
1
1
```