XOR 삼형제 2

면접 대비

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

요약

1부터 N까지 수 중에서 서로 다른 세 수의 xor이 0이 되지 않는 가장 큰 연속 구간을 시작 수가 가장 작은 것으로 고릅니다.

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

문제

서로 다른 세 양의 정수 $a$ , $b$ , $c$ 가 $a \oplus b \oplus c = 0$ 을 만족하면 이 세 수를 XOR 삼형제라고 부른다. $\oplus$ 는 비트 단위 배타적 논리합이다.

정수 $N$ 이 주어진다. $1$ 부터 $N$ 까지의 정수 중에서 몇 개를 고르되, 고른 수 가운데 어떤 세 수도 XOR 삼형제를 이루지 않아야 한다. 이 조건을 지키면서 가장 많이 고르는 방법을 찾아라.

입력

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

이어지는 $T$ 개의 줄에 각각 정수 $N$ 이 하나씩 주어진다. ( $1 \le N \le 100$ )

출력

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

첫 줄에는 고른 수의 최대 개수를 출력한다.

둘째 줄에는 고른 수를 오름차순으로, 공백 하나로 구분해 출력한다.

최대 개수를 이루는 선택이 여러 가지일 수 있으므로 출력할 답을 하나로 정한다. $1 \le N \le 100$ 인 모든 $N$ 에서, 최대 개수를 이루면서 연속한 정수로만 이루어진 선택이 항상 존재한다. 그 선택을 출력한다. 그런 선택이 둘 이상이면 첫 수가 가장 작은 것을 출력한다.

예제2

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