Đồ thị nguyên tố

Cho số nguyên dương $n$. Hãy xây dựng một đồ thị vô hướng đơn (không có cạnh kép, không có khuyên) thỏa mãn đồng thời các điều kiện sau:

1. Đồ thị có đúng $n$ đỉnh, đánh số từ $1$ đến $n$.
2. Tổng số cạnh $m$ là một số nguyên tố.
3. Bậc (số cạnh kề) của mỗi đỉnh là một số nguyên tố.

Đồ thị có thể không liên thông.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$ ($3\le n\le 1000$).

Dữ liệu ra

• Nếu không tồn tại đồ thị thỏa mãn, in ra $-1$.
• Ngược lại, dòng đầu in số nguyên tố $m$ ($2\le m\le \frac{n(n-1)}{2}$) — số cạnh của đồ thị. Sau đó in $m$ dòng, mỗi dòng chứa hai số nguyên $u_i,v_i$ ($1\le u_i,v_i\le n$) mô tả một cạnh nối $u_i$ và $v_i$.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $3\le n\le 1000$.

Ví dụ

Ghi chú

Bộ chấm sẽ kiểm tra rằng đồ thị bạn đưa ra hợp lệ (đơn, không khuyên, đúng $n$ đỉnh), số cạnh nguyên tố và bậc mỗi đỉnh nguyên tố.