Директор цирка выбирал новый номер для своей программы. Конкурс выиграл Танец Блох. В Танце Блох одновременно участвуют N блох, пронумерованных от 1 до N. Танец исполняется на полосе, состоящей из N клеток. Задано N стрелок, нарисованных от клетки к клетке таким образом, что в каждой клетке начинается ровно одна стрелка, и в каждой ровно одна заканчивается. В начале блохи стоят на клетках, номера которых совпадают с номерами блох. Каждую секунду каждая блоха прыгает со своей клетки на другую по стрелке (все блохи прыгают одновременно). Танец Блох заканчивается, когда все блохи оказываются на начальных клетках. Директор хочет, чтобы номер продолжался как можно дольше. Необходимо найти расстановку стрелок.

Напишите программу, которая вводит из файла Circus.in количество блох N (1 <= N <= 80) и находит, каким образом нарисовать стрелки, чтобы представление продолжалось максимально долго. Программа также должна выводить длительность номера в секундах.

Формат вывода:

Вывод осуществляется в файл Circus.out. В первой строке выводится набор из N пар чисел через пробел, каждая пара определяет позицию начала и позицию конца стрелки. Например, пара 5 3 означает, что из клетки 5 следует переместиться в клетку 3. Во вторую строку вывести продолжительность номера в секундах.

Пример ввода 1 5	Пример вывода 1 1 2 2 1 3 4 4 5 5 3 6
Пример ввода 2 8	Пример вывода 2 1 2 2 3 3 1 4 5 5 6 6 7 7 8 8 4 15