背景

小花妹妹收到了一串密文，但是由于接收器坏了，重复接收了多次。小花妹妹哭了，拔下了电源导致最后一遍也不一定完整。她现在想知道这段密文最短可能长度是多少。

格式

输入

第一行输入一个正整数 L (1 < L <= 1000)表示这个字符串的长度。

输出

输出最短的可能长度。

样例

输入

8
cabcabca

输出

3

限制

100ms, 1024KiB for each test case.