Hãy xây dựng một đồ thị có hướng có không quá \(5 \times 10^5\) đỉnh và \(10^6\) cạnh sao cho thỏa mãn các điều kiện sau:

• Giữa hai đỉnh chỉ được có tối đa một cạnh;
• Không tồn tại chu trình;
• Có chính xác \(k\) đường đi giữa đỉnh \(1\) và đỉnh có chỉ số lớn nhất.

Yêu cầu

• Hãy xây dựng một đồ thị bất kỳ thỏa mãn các điều kiện trên.

Input

• Dòng đầu tiên chứa số nguyên \(k\) (\(1 \le k \le 10^{100}\)).

Output

• Dòng đầu tiên chứa hai số nguyên \(N, M\) lần lượt thể hiện số đỉnh và số cạnh trong đồ thị của bạn.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) mô tả một cạnh nối một chiều từ đỉnh \(u\) đến đỉnh \(v\).

Example

4

6 8
1 2
1 3
1 4
1 5
2 6
3 6
4 6
5 6