\documentclass{article}

\usepackage{geometry}
\usepackage{verbatim}
\usepackage{tabularx}
\usepackage{graphicx}
\usepackage{etoolbox}

\ifdefined\testinputfile\endcsname\else\input ../../../pacnw/ReadSamples.tex\fi

\title{Repeating Goldbachs}
\problemname{RepeatingGoldbachs}
\date{}

\begin{document}
\maketitle
\begin{figure}[h!]
\centering
\includegraphics[width=0.6\textwidth]{RepeatingGoldbachs.png}
\end{figure}


The Goldbach Conjecture states that any even number $x \ge 4$ can be
expressed as the sum of two primes. It can be verified that the
conjecture is true for all $x \le 10^6$.

Define a \emph{Goldbach step} as taking $x$ ($4 \le x \le 10^6$),
finding primes $p$ and $q$ (with $p \le q$) that sum to $x$,
and replacing $x$ with $q-p$.
If there are multiple pairs of primes which sum to $x$, we take
the pair with the largest difference.
That difference must be even and less than $x$.
Therefore, we can repeat more Goldbach steps, until we can reach
a number less than 4.

Given $x$, find how many Goldbach steps it takes until reaching
a number less than 4.

\section{Input}

The input will consist of a single integer $x$ ($4 \le x \le 10^6$).

\section{Output}

Print, on a single line, the number of Goldbach steps it takes to
reach a number less than 4.

\sampleio{RepeatingGoldbachs}

\end{document}
