32105번 - James Ferraro - Live at Primavera Sound 2012 스페셜 저지

문제

병윤이는 합이 소수가 되는 쌍을 찾는 문제에는 질렸다. 이번에는 합이 두 소수의 곱이 되는 쌍을 찾으려고 한다. 양의 정수 $N$이 주어지면 1ドル$ 이상 $N$ 이하의 정수들 중 합이 어떤 두 소수의 곱이 되도록 하는 두 수의 쌍을 최대한 많이 골라야 한다. 이때 두 소수는 같아도 되며, 1ドル$부터 $N$까지의 수는 각각 최대 한 번만 고를 수 있다.

입력

첫째 줄에 정수 $N$이 주어진다. $(1 \le N \le 100,000円)$

출력

첫째 줄에 조건을 만족하는 쌍의 개수 $K$를 출력한다.

다음 $K$개 줄에 걸쳐 조건을 만족하는 쌍을 출력한다. 각 줄에는 두 정수를 공백으로 구분하여 출력한다. 두 정수의 합은 두 소수의 곱이어야 하고, 1ドル$ 이상 $N$ 이하의 수를 각각 최대 한 번만 출력해야 한다.

조건을 만족하는 쌍이 여러 가지일 경우 그중 아무거나 출력한다.

제한

힌트