말더듬이 없는 수열

문자로 이루어진 수열을 생각한다. 수열 $x_1, x_2, \dots, x_n$ 에서 어떤 연속한 블록 바로 뒤에 그것과 똑같은 블록이 이어지면, 이 수열은 말더듬(stammer) 을 포함한다고 한다. 정확히는, $1 \le i < j$ 이고 $2j - i - 1 \le n$ 인 두 첨자 $i$, $j$ 가 존재하여

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

이 성립하는 경우를 말한다. 다시 말해, 비어 있지 않은 어떤 단어 $w$ 에 대해 $ww$ 꼴의 부분 문자열(제곱)을 포함하는 경우이다. 이러한 반복 블록이 하나도 없는 수열을 말더듬이 없는 수열이라고 부른다.

길이가 $n$ 인 말더듬이 없는 수열을, 되도록 적은 종류의 문자만으로 만들고자 한다.

몇 가지 사실:

• 문자를 한 종류만 쓰면 말더듬이 없는 수열의 길이는 최대 $1$ 이다. $aa$ 자체가 이미 말더듬이기 때문이다.
• 문자를 두 종류($a$, $b$) 쓰면 말더듬이 없는 수열의 최대 길이는 $3$ 이며, 그러한 수열은 정확히 $aba$ 와 $bab$ 뿐이다. 예를 들어 $babab$ 은 말더듬이 없는 수열이 아니다(블록 $ba$ 와 블록 $ab$ 가 각각 반복된다).
• 문자를 세 종류 쓰면 모든 길이에 대해 말더듬이 없는 수열이 존재한다. 예를 들어 $abcab$ 은 길이가 $5$ 인 말더듬이 없는 수열이다.

필요한 문자 종류의 최소 개수를 구하여라.

표준 입력의 첫째 줄에 양의 정수 $n$ ($1 \le n \le 10{,}000{,}000$) 이 주어진다. 만들고자 하는 수열의 길이이다.

길이가 $n$ 인 말더듬이 없는 수열에 반드시 나타나야 하는 서로 다른 문자의 최소 개수 $k$ 를 한 줄에 출력한다.