Все знают, что хоббиты любят устраивать различные вечеринки и празднества. В Шире живет n хоббитов. Они решили провести Грандиозный Праздник (ГП), длящийся несколько дней. На каждый день был составлен список приглашенных — некоторое непустое подмножество из всех жителей Шира. Для того чтобы всем было весело, и никто не скучал, необходимо чтобы для любых двух разных дней (скажем, А и В) ГП существовал бы хотя бы один хоббит, приглашенный как в день А, так и в день В. Однако, чтобы никто не поссорился, для любых трех разных дней А, В, С не должно существовать хоббита, приглашенного в день А, В и С. Жители Шира заинтересованы в наибольшей продолжительности ГП. Ваша задача для данного числа n указать наибольшую продолжительность ГП и списки приглашенных на каждый день.
Выходные данные
В первой строке выходного файла выведите число k — наибольшую продолжительность ГП в днях. Далее в k строках выведите списки приглашенных (через пробел). Каждый список выводите на отдельной строке. Каждый список может содержать произвольное положительное количество хоббитов. Хоббиты нумеруются целыми числами от 1 до n.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
|
3
1 2
1 3
2 3
|
|
2
|
5
|
3
1 2
1 3
2 3
|