[Poi2003] Sequences without Stammers

对于字符序列 $x_1x_2\ldots x_n$ ，如果其中存在两个相邻且完全相同的连续子串，则称该序列包含一个“口吃”（stammer）。

具体而言，如果存在整数 $i$ 和 $j$ ，满足

1\le i<j\le \frac{n+i+1}{2},

并且

x_i=x_j,\ x_{i+1}=x_{j+1},\ \ldots,\ x_{j-1}=x_{2j-i-1},

那么子串 $x_ix_{i+1}\ldots x_{j-1}$ 与紧随其后的子串 $x_jx_{j+1}\ldots x_{2j-i-1}$ 完全相同，因此该序列包含“口吃”。

给定序列长度 $n$ ，求构造一个不包含“口吃”的字符序列至少需要使用多少种不同的字符。

例如，当 $n=3$ 时，只需使用字符 $a$ 和 $b$ ，序列 $aba$ 和 $bab$ 均不包含“口吃”。当 $n=5$ 时，至少需要使用 $3$ 种字符，例如 $abcab$ 是一个合法序列。

输入格式

输入仅一行，包含一个整数 $n$ 。

输出一行一个整数，表示构造长度为 $n$ 且不包含“口吃”的字符序列所需的最少字符种类数。

本题为 POI 2003 试题「Sequences without Stammers」，题面与测试数据整理自 BZOJ。