저항값이 $1\,[\Omega]$인 저항만을 사용하여 저항값이 $\sqrt{D}\,[\Omega]$인 저항을 구성하시오.

양의 정수 $D$가 주어진다. 다음 조건을 모두 만족하는 연결된 무방향 그래프를 하나 구성하시오. 이 문제의 제약 조건 하에서 그러한 그래프는 항상 존재함이 증명될 수 있다.

• 정점의 개수 $N$은 $2$ 이상 $300$ 이하이며, 각 정점은 $1$부터 $N$까지의 서로 다른 번호를 가진다.
• 간선의 개수 $M$은 $300$ 이하이며, 자기 루프와 다중 간선이 허용된다.
• 아래에 정의된 "정점 $1$에서 정점 $N$까지의 유효 저항"은 $\sqrt{D}$와 $\pm 10^{-6}$의 절대 오차 범위 내에 있어야 한다.

$G$를 $n$개의 정점과 $m$개의 간선을 가진 연결된 무방향 그래프($n \ge 2$)라고 하고, $j$번째 간선이 정점 $a_j, b_j$를 연결한다고 하자. 그래프 $G$의 각 정점에 실수 $V_i(i = 1, 2, \dots, n)$를, 각 간선에 실수 $I_j(j = 1, 2, \dots, m)$를 할당하여 다음 모든 방정식을 만족하도록 한다.

• $I_j = V_{a_j} - V_{b_j} \quad (j = 1, 2, \dots, m)$
• $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0 \quad (i = 2, 3, \dots, n - 1)$
• $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$

이러한 할당은 항상 존재하며, 나아가 $V_1 - V_n$의 값은 유일하게 결정됨이 증명될 수 있다. 이 값을 "정점 $1$에서 정점 $n$까지의 유효 저항"으로 정의한다.

입력

입력은 하나의 양의 정수 $D$로 구성된다. ($1 \le D \le 5000$)

출력

첫 번째 줄에 구성한 그래프의 정점 개수 $N$과 간선 개수 $M$을 이 순서대로 공백으로 구분하여 출력한다.

이어지는 $M$개의 각 줄에는 $i$번째 줄($i = 1, 2, \dots, M$)에 $i$번째로 선택한 간선의 양 끝점을 공백으로 구분하여 출력한다.

조건을 만족하는 그래프가 여러 개 존재할 경우, 그중 아무거나 출력해도 된다.

예제

입력 1

1

출력 1

4 5
1 2
1 3
2 3
2 4
3 4

참고

첫 번째 예제에 대한 출력의 예시는 다음과 같다.

정점 $1$에서 정점 $n$까지의 유효 저항이 $1\,[\Omega]$이라는 것은 다음과 같이 설명할 수 있다.

• 모든 저항의 저항값이 $1\,[\Omega]$이고, 대칭성에 의해 정점 $2$와 $3$의 전위가 같으므로, 그 사이의 저항은 없는 것으로 취급할 수 있다.

• 결과적으로 회로는 병렬로 연결된 두 개의 가지로 축소되며, 각 가지는 $1\,[\Omega]$ 저항 두 개가 직렬로 연결된 형태이다.

• $1\,[\Omega]$ 저항 두 개를 직렬로 연결한 유효 저항은 $2\,[\Omega]$이며, $2\,[\Omega]$ 저항 두 개를 병렬로 연결한 유효 저항은 $1\,[\Omega]$이다.

다음 출력 또한 올바른 것으로 간주된다.

2 1
1 2