Description

You plan to print a sequence of letters on paper.

To accomplish this, you decide to carve a stamp. Each use of the stamp prints all the letters on the stamp onto the paper.

The same character at the same position may be printed multiple times. For example: using the stamp aba can produce ababa (the middle a is printed twice). However, since what has been printed cannot be erased, printing different characters at the same position is not allowed. For example: using the stamp aba cannot produce abcba.

Because carving a stamp is not easy, you want the length of the stamp string to be as small as possible.

Input Format

A non-empty string of length at most $5 \times 10^5$ (containing only lowercase letters), representing the string you want to print on the paper.

Output Format

Output a single integer, the minimal possible length of the stamp string.

ababbababbabababbabababbababbaba

8

Hint

A stamp is ababbaba.

The printing process is as follows:

ababbababbabababbabababbababbaba
ababbaba
     ababbaba
            ababbaba
                   ababbaba
                        ababbaba

Translated by ChatGPT 5