Зиниум – чудо нашего мира, а может быть, и всех миров. Найденный в конце XIX века при раскопках древнеримских поселений на территории современной Албании, Зиниум принадлежал самому Юлию Цезарю и был утрачен им в его последнем походе.

Артефакт представляет собой шахматную доску размером N*N клеток. Клетка в левом нижнем её углу имеет координаты (1, 1), а клетка в правом верхнем углу – координаты (N, N). По легенде, если на доске расставить N ферзей таким образом, что ни один из них не будет атаковать другого, то освобождённая энергия Зиниума изменит мир до неузнаваемости. Реки повернутся вспять, небо упадёт на землю, люди научатся называть вещи своими именами... Может быть, даже Петя Великолепный примет участие в очередном контесте Timus Top Coders. А может быть, и нет. Самое время проверить.

Единственная строка содержит целое число N (4 ≤ N ≤ 100000).

Для каждого ферзя в отдельной строке вывести через пробел координаты его клетки. Ферзи могут быть перечислены в произвольном порядке. Если задача имеет несколько решений, то вывести любое из них.

Два ферзя атакуют друг друга, если находятся в клетках, расположенных одной и той же горизонтали, вертикали или диагонали.