In ra tất cả cặp số nguyên tố \(A,B(A\le B)\) thỏa mãn \(A+B\) cũng là số nguyên tố và \(A+B\le N\). (In theo thứ tự từ điển từ bé đến lớn)

Input

• Dòng thứ nhất chứa số nguyên dương \(N(1\le N\le 10^6)\)

Output

• Dòng thứ nhất in ra số \(k\) - số lượng cặp \((A,B)\) thỏa mãn yêu cầu bài toán

• In ra \(k\) cặp \((A,B)\) thỏa mãn yêu cầu bài toán (theo thứ tự từ điển từ bé đến lớn).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0<N\le 10\)

• Subtask \(2\) (\(20\%\) số điểm): \(0<N\le 10^4\)

• Subtask \(3\) (\(60\%\) số điểm): \(\text{Còn lại}\)

Example

7

2
2 3
2 5