Portal ↬\looparrowright

You are given an integer nn.
You should find a list of pairs (x1,y1),(x2,y2),⋯ ,(xq,yq)(x_1,y_1), (x_2,y_2),\cdots, (x_q,y_q) (1≤xi,yi≤n1≤x_i,y_i≤n) satisfying the following condition.
Let’s consider some function f:N×N→Nf:\mathbb N\times\mathbb N→\mathbb N (we define N\mathbb N as the set of positive integers). In other words, ff is a function that returns a positive integer for a pair of positive integers.
Let’s make an array a1,a2,⋯ ,ana_1,a_2,\cdots,a_n, where ai=ia_i=i initially.
You will perform qq operations, in ii-th of them you will:

  1. assign t=f(axi,ayit=f(a_{x_i},a_{y_i} (tt is a temporary variable, it is used only for the next two assignments);

  2. assign axi=ta_{x_i}=t;

  3. assign ayi=ta_{y_i}=t.

In other words, you need to simultaneously change axia_{x_i} and ayia_{y_i} to f(axi,ayi)f(a_{x_i},a_{y_i}). Note that during this process f(p,q)f(p,q) is always the same for a fixed pair of pp and qq.
In the end, there should be at most two different numbers in the array a.
It should be true for any function ff.
Find any possible list of pairs. The number of pairs should not exceed 5×1055\times 10^5.

Input

The single line contains a single integer nn (1≤n≤150001≤n≤15000).

Output

In the first line print qq (0≤q≤5×1050≤q≤5\times 10^5) — the number of pairs.
In each of the next qq lines print two integers. In the ii-th line print xi,yix_i, y_i (1≤xi,yi≤n1≤x_i,y_i≤n).
The condition described in the statement should be satisfied.
If there exists multiple answers you can print any of them.

Examples

input

1
3

output

1
2
1
1 2

input

1
4

output

1
2
3
2
1 2
3 4

Note

In the first example, after performing the only operation the array aa will be [f(a1,a2),f(a1,a2),a3][f(a_1,a_2),f(a_1,a_2),a_3]. It will always have at most two different numbers.
In the second example, after performing two operations the array aa will be [f(a1,a2),f(a1,a2),f(a3,a4),f(a3,a4)][f(a_1,a_2),f(a_1,a_2),f(a_3,a_4),f(a_3,a_4)]. It will always have at most two different numbers.

Translation

定义二元函数 f(x,y)f (x,y )，定义域为正整数对，值域为正整数，映射方式未知。自变量相同的时候保证函数值相同。
给一个长度为 nn 的序列 aa，初始时 ai=ia_i=i。每次可以选择两个数
$x_ i , y_ i ∈ [ 1 , n ] $，令 axi=ayi=f(axi,ayi)a_{x_i}=a_{y_i}=f(a_{x_i},a_{y_i})，你需要构造一个操作顺序使得不论 ff 函数如何定义,最终操作的结果都能使序列中不相同数的个数不超过 22。

Idea

那么不妨考虑四个数的情况.
先操作 1,21 , 2，再操作 3,43 , 4，然后操作 1,31 , 3 和 2,42 , 4 ，此时四个数完全一样。类似的，∀ t∈N∗\forall\ t\in\mathbb N^\ast，长度为 2t2^t 的序列，都能经过若干次操作变成同一数值。下面用数学归纳法证明：当 t=1t=1 时，操作 1,21,2，显然成立；假设当 t=kt=k 时上述命题成立；那么当 t=k+1t=k+1 时，首先将序列前 2k2^{k} 个数变为 uu，再将序列后 2k2^k 个数字变成 vv，接着依次操作 i,i+2ki,i+2^{k}，其中 i∈N∗i\in\mathbb N^\ast 且 1⩽i⩽2k1\leqslant i\leqslant 2^k，最终将所有数字变成 f(u,v)f(u,v)，证毕。
令 ctc_t 表示序列长度为 2t2^t 时，将所有数字变为同一数值的操作次数。那么有 ct=2ct−1+2t−1c_t=2c_{t-1}+2^{t-1}，且 c1=1c_1=1，得 ct=t⋅2t−1c_t=t\cdot2^{t-1}。
对于长度为 nn 的序列，取 limlim 为使得 2lim≤n2^{lim} \leq n 的最大正整数。我们先用 climc_{lim} 步把前 2lim2^{lim} 个数字变成 uu，再用 climc_{lim} 步把后 2lim2^{lim} 个数字变为 vv。由于 2lim+1>n2^{lim+1}>n，最终序列只会包含 uu 和 vv。
由于 n≤15000n\le15000，故 limlim 的最大值为 ⌊log⁡215000⌋=13\left\lfloor\log_215000\right\rfloor=13，最大操作次数为 2c13=106496<5×1052c_{13}=106496<5\times10^5，满足条件。
采用递归分治法求得方案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1408F
Date: 10/2/2020
Description: Constructive
*******************************************************************/
#include<vector>
#include<cstdio>
#include<utility>
#include<iostream>
using namespace std;
vector<pair<int,int>>ans;
int n;
int lim;
void DFS(int l,int r){
	if(l==r){
		return;
	}
	int mid=l+r>>1;
	DFS(l,mid);
	DFS(mid+1,r);
	for(register int i=l,j=mid+1;i<=mid;i++,j++){
		ans.push_back(make_pair(i,j));
	}
}
int main(){
	cin>>n;
	while(1<<lim<=n){
		lim++;
	}
	lim--;
	DFS(1,1<<lim);
	DFS(n-(1<<lim)+1,n);
	cout<<ans.size()<<endl;
	for(auto x:ans){
		printf("%d %d\n",x.first,x.second);
	}
	return 0;
}