Byteasar 想要在他的房子上装饰一段很长的图案。为此，他必须先准备一个刻有字母的模板。他将通过把模板放置在墙上的适当位置并进行喷涂来装饰墙面。这样，他可以一次性“印出”模板上的所有字母（无法只“印出”其中的一部分）。当然，由于多次使用模板，墙上的某些字母可能会被重复喷涂。模板上的字母是连续的（中间没有空格）。当然，他也可以准备一个包含整个图案的模板。但 Byteasar 希望尽可能降低成本，因此他想让模板的长度尽可能短。
编写一个程序：
- 从标准输入读取 Byteasar 想要装饰在房子上的图案。
- 确定实现该图案所需模板的最小长度。
- 将结果写入标准输出。
输入格式
标准输入的唯一一行包含一个单词，即 Byteasar 想要装饰在房子上的图案。它由不少于 1 个且不超过 500,000 个小写英文字母组成。
输出格式
标准输出的唯一一行应写入一个整数，即模板中字母的最小数量。
样例
输入 1
ababbababbabababbabababbababbaba
输出 1
8
