시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB124436.364%

문제

Laika has decided to make a gift for her good friend Azusa, the witch of the highlands. For reasons we do not know, this gift will be a finite set of positive integers. If that were all, it would be a simple matter to choose a gift, but several factors complicate this.

First of all, Laika’s rival, Flatorte, has mysterious magical powers: given two integers $x$ and $y$ she can create the greatest common divisor of $x$ and $y$ (i.e. $\gcd(x, y)$). If Laika gave a gift that Flatorte could immediately add to (i.e. if she gifted a set A for which $x, y ∈ A$, yet $\gcd(x, y) \not∈ A$), then Flatorte would immediately tease her rival. Therefore, Laika’s gift must not be improvable using Flatorte’s powers: if she gifts $A$ then for all $x, y ∈ A$ it must be the case that $\gcd(x, y) ∈ A$.

Secondly, Laika wants the gift to have a certain special significance. It has been $K$ days since she met Azusa, and she wants the gift to show this fact. Therefore, she has arranged all of the sets that satisfy the condition explained above in Laikan order (explained below), getting an infinite sequence of finite sets $S_0, S_1, \dots$. She wants to select and gift set $S_K$. Can you help her do so?

Laikan order. Take two sets $A$ and $B$. Then, $A$ comes before $B$ in Laikan order if and only if $\max A < \max B$, or $\max A = \max B$ and $A \setminus \{\max A\}$ comes before $B \setminus \{\max B\}$ in Laikan order. For the purposes of this definition, take $\max ∅ = −∞$. Note that this is always well defined for finite sets of positive integers.

입력

The first line of the input contains a single integer $T$, the number of test cases in this file. The next $T$ lines each contain a value of $K$ for which we want to know $S_K$.

출력

For each of the $T$ values of $K$, output the set $S_K$. To output a set, output a line that begins with the number of elements it has, and the continues with its elements, in increasing order.

제한

  • $1 ≤ T ≤ 5$

서브태스크

번호배점제한
18

$0 ≤ K ≤ 100$

221

$0 ≤ K ≤ 1\,000\,000$

341

$0 ≤ K ≤ 500\,000\,000$

414

$0 ≤ K ≤ 1\,000\,000\,000$

516

$0 ≤ K ≤ 1\,500\,000\,000$

예제 입력 1

5
0
1
2
3
4

예제 출력 1

0
1 1
1 2
2 1 2
1 3

예제 입력 2

4
5
6
100
1000

예제 출력 2

2 1 3
3 1 2 3
5 1 2 3 7 8
7 1 2 3 5 10 11 12

힌트

Note that $S_0 = ∅$, $S_1 = \{1\}$, $S_2 = \{2\}$, $S_3 = \{1, 2\}$, $S_4 = \{3\}$, $S_5 = \{1, 3\}$, $S_6 = \{1, 2, 3\}$, $S_{100} = \{1, 2, 3, 7, 8\}$, $S_{1000} = \{1, 2, 3, 5, 10, 11, 12\}$. These are precisely the sets outputted in the examples (together with their sizes). Observe that $S_6 \ne \{2, 3\}$ — this is because $2, 3 ∈ \{2, 3\}$, yet $\gcd(2, 3) = 1 \not∈ \{2, 3\}$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.