Вадим придумал новую шахматную фигуру, которую он назвал растаманом. Растаман обязан стоять в центре клетки, он не двигается по полю, но смотрит абсолютно во всех направлениях. Если он видит какую-то фигуру, то он относится к ней спокойно, а вот если какую-то фигуру он увидеть не может (просмотр загорожен другой фигурой; в данной задаче вы можете считать, что каждая фигура является точкой; просмотр загорожен, если на отрезке между двумя фигурами стоит другая), то растаман может побить её. Ниже приведены примеры случаев, когда растаман (M) бьёт другую фигуру (E), потому что другая фигура (F) загораживает её:

Ваша задача заключается в том, чтобы расставить на шахматной доске размера N × N ровно N растаманов так, чтобы никакие два не били друг друга.

В единственной строке ввода даётся целое число N — размер шахматной доски (2 ≤ N ≤ 1000).

Выведите N пар чисел x_i и y_i — строка и столбец клетки, в которой стоит i-й растаман. Все клетки должны быть попарно различными, а также никакой растаман не может бить другого растамана.

Гарантируется, что ответ существует. Если есть несколько решений, выведите любое из них.