F. Два различных
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$.

Вы должны найти список пар $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, ..., $$$(x_q, y_q)$$$ ($$$1 \leq x_i, y_i \leq n$$$) который удовлетворяет следующему условию.

Рассмотрим некоторую функцию $$$f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$$$ (мы определяем $$$\mathbb{N}$$$ как множество положительных целых чисел). Другими словами, $$$f$$$ это функция, возвращающая положительное целое число по паре положительных целых чисел.

Давайте рассмотрим массив $$$a_1, a_2, \ldots, a_n$$$, где изначально $$$a_i = i$$$.

Вы сделаете $$$q$$$ операций, в $$$i$$$-й из них вы сделаете:

  1. присвоите $$$t = f(a_{x_i}, a_{y_i})$$$ ($$$t$$$ это временная переменная, она используется только для следующих двух присвоений);
  2. присвоите $$$a_{x_i} = t$$$;
  3. присвоите $$$a_{y_i} = t$$$.

Другими словами, вам нужно одновременно заменить $$$a_{x_i}$$$ и $$$a_{y_i}$$$ на $$$f(a_{x_i}, a_{y_i})$$$. Обратите внимание, что в течение процесса значение $$$f(p, q)$$$ всегда одинаково для заданных положительных целых чисел $$$p$$$ и $$$q$$$.

В конце должно быть не больше двух различных чисел в массиве $$$a$$$.

Это должно быть выполнено для любой функции $$$f$$$.

Найдите любой возможный список пар. Количество пар должно не превосходить $$$5 \cdot 10^5$$$.

Входные данные

В единственной строке находится единственное целое число $$$n$$$ ($$$1 \leq n \leq 15\,000$$$).

Выходные данные

В первой строке выведите $$$q$$$ ($$$0 \leq q \leq 5 \cdot 10^5$$$) — количество пар.

В каждой из следующих $$$q$$$ строк выведите по два целых числа. В $$$i$$$-й строке выведите $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$).

Условие, описанное в тексте условия задачи, должно быть удовлетворено.

Если есть несколько возможных ответов, выведите любой.

Примеры
Входные данные
3
Выходные данные
1
1 2
Входные данные
4
Выходные данные
2
1 2
3 4
Примечание

В первом тесте после применения единственной операции массив $$$a$$$ будет $$$[f(a_1, a_2), f(a_1, a_2), a_3]$$$. В нем всегда не больше двух различных чисел.

Во втором тесте после применения двух операций массив $$$a$$$ будет $$$[f(a_1, a_2), f(a_1, a_2), f(a_3, a_4), f(a_3, a_4)]$$$. В нем всегда не больше двух различных чисел.