29261번 - 소수 세기

소수는 $1$과 자신만을 양의 약수로 가지는 $2$ 이상의 정수이다. 한별이는 고독한 수인 소수를 세며 용기를 얻기로 했다. 하지만 일반적인 방식으로 소수를 세는 일은 너무 많이 했기 때문에, 이번에는 아래의 방식을 사용해 보려고 한다.

맨 처음 한별이는 칠판에 소수 $P$를 적는다. 그리 다음의 과정을 반복한다.

• 칠판에 적힌 수 중, $p_1 + p_2 + 1$(단, $p_1$, $p_2$는 소수) 꼴로 표현되는 수가 있으면 그러한 수 중 하나를 골라 지우고, 대신에 $p_1$과 $p_2$를 적는다. 만약 고른 수에 대해서 가능한 $(p_1, p_2)$ 쌍이 여러 개 있으면 그런 쌍 중 하나를 고른다.

이 방식대로 진행할 때, 지워진 수를 포함하여 한별이가 소수를 적는 최대 횟수를 구하자.

첫 번째 줄에 소수 $P$가 주어진다. ($2 \leq P < 3\,000\,000$)

첫 번째 줄에 지워진 수를 포함하여 한별이가 소수를 적는 최대 횟수를 출력한다.