At the beginning of the 18th century, a group of European explorers arrived on an island inhabited by a group of tribes that had never come into contact with representatives of European civilization.
To successfully establish contacts with the natives, the leader of the group plans to give a gift to the leader of each tribe he meets. To this end, he brought a long chain of glass, similar to precious stones.
Let's represent the string as a string s, consisting of small letters of the English alphabet, where each letter means the type of piece of glass at the corresponding position.
The researchers are going to cut the chain into some fragments, and then hand over exactly one fragment to the leader of each tribe encountered by the group. The research leader decided to split the chain into fragments according to the following rules:
- In order not to spend a lot of time on cutting, each fragment should be a group of adjacent pieces of glass in the chain, that is, a substring of the string s.
- All pieces of glass must be used, that is, each piece of glass must be included in exactly one fragment.
- Because the researchers don't know how the aborigines will value certain types of glass, they want each chief to get the same set of glass without regard to order. In other words, for any type of glass, the number of glass of this type must be the same in each of the fragments.
- Researchers don't know how many tribes live on the island, so the number of prepared fragments should be as large as possible.
Help the manager determine the maximum number of fragments that can be obtained.
Input:
The first line contains the string s (1 <= |s| <= 5000000).
Output:
Print a single number - the maximum possible number of fragments into which the researchers can cut the chain they have without violating any of the conditions formulated by the group leader.
Examples:
| Input |
Output |
| abbabbbab |
3 |
| aabb |
1 |
Explanations:
In the first example, researchers can break the chain 'abbabbbab' fragments 'abb', 'abb', 'bab', then the leader of each tribe they meet will get one glass of type 'a' and two pieces of 'b'.
In the second example, the string cannot be divided into more than one fragment of the chain, observing all the conditions.