描述

给定一个正整数 (n)，令 (N) 为从 (1) 到 (n) 的整数集合。有限子集序列 (A_1, \cdots, A_k) 满足以下条件时被称为完全多样化序列： a. 每个子集 (A_i) 都包含偶数个元素。 b. 对于 (N) 中的每个元素 (m)，在该序列中恰好有 (m) 个集合 (A_i) 包含 (m) 作为其成员。

例如，子集序列 ({1,3})，({2,3})，({2,3}) 是集合 ({1,2,3}) 的一个完全多样化序列。（注意，序列中的子集可能是相同的。）

如果不存在其他集合 (N) 的完全多样化序列，其序列元素数量比某个完全多样化序列更少，那么这个集合 (N) 的完全多样化序列就被称为最小完全多样化序列。上述例子是最小的，因为元素 (3) 必须出现在 (3) 个不同的集合中。

编写一个程序，对于给定的整数 (n)，判断是否存在对应的集合 (N) 的完全多样化序列，如果存在完全多样化序列，则找到集合 (N) 的一个最小完全多样化序列。

输入

输入将是一个正整数 (n) 的序列，每行一个，随后在另一行输入一个 (0) 表示输入结束。

输出

如果不存在对应的集合 (N) 的完全多样化序列，则在一行中输出一个 (0)，后面跟一个空行。

如果存在对应的集合 (N) 的完全多样化序列，则在一行中输出你找到的最小序列中的集合数量，然后每行输出一个集合，之后跟一个空行。

每个集合的元素应以升序输出，数字之间用单个空格分隔。序列中的集合应以字典序输出。每个问题可能有许多可能的解决方案。

输入数据 1

8
9
11
17
23
0

输出数据 1

8
1 3 5 6 7 8
2 4 5 6 7 8
2 4 5 6 7 8
3 4 5 6 7 8
3 4 5 6 7 8
6 8
7 8
7 8

0

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

0

23
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
9 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
12 13 14 15 16 17 18 19 20 21 22 23
13 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
16 17 18 19 20 21 22 23
17 19 20 21 22 23
18 19 20 21 22 23
18 19 20 21 22 23
20 21 22 23
21 23
22 23
22 23

题目来源

大纽约地区 2003 年竞赛