Sequences without Stammers

We work with sequences of letters. A sequence $x_1, x_2, \dots, x_n$ contains a stammer if some block of consecutive letters is immediately followed by an identical block. Formally, there exist indices $i$ and $j$ with $1 \le i < j$ and $2j - i - 1 \le n$ such that

$x_{i} = x_{j},\; x_{i+1} = x_{j+1},\; \dots,\; x_{j-1} = x_{2j-i-1}.$

Equivalently, the sequence contains a square: a factor of the form $ww$ for some non-empty word $w$. A sequence with no such repeated block is called stammer-free.

We want to build a stammer-free sequence of length $n$ using as few distinct letters as possible.

Some observations:

• With a single letter, the only stammer-free sequences have length $1$, because $aa$ is already a stammer.
• With two letters, say $a$ and $b$, the longest stammer-free sequences have length $3$: exactly $aba$ and $bab$. For example, $babab$ is not stammer-free (the block $ba$ and the block $ab$ each repeat).
• With three letters, a stammer-free sequence exists for every length; for instance $abcab$ is a stammer-free sequence of length $5$.

Determine the minimal number of different letters needed.

The first line of standard input contains one positive integer $n$ ($1 \le n \le 10{,}000{,}000$) — the desired length of the sequence.

Print a single positive integer $k$: the minimal number of distinct letters that must appear in any stammer-free sequence of length $n$.