Culture Contact

At the beginning of the 16th century, a group of European explorers arrived at an island inhabited by several tribes that had never seen a person from Europe.

To establish friendship with the islanders, the group leader plans to give a present to the head of each local tribe the explorers meet on their way. The leader brought a long chain of glass pieces that look similar to jewels. Treat the chain as a string $s$ of lowercase English letters, where each letter gives the type of glass piece at that position.

The explorers cut the chain into fragments and give exactly one fragment to the head of each tribe they meet. The group leader divides the chain according to these rules:

• Each fragment is a contiguous group of glass pieces, that is, a substring of $s$.
• Every glass piece is used, so each piece belongs to exactly one fragment.
• Each tribe head must receive the same set of glass pieces, ignoring order. For each glass piece type, the count in every fragment must be the same.

The explorers do not know how many tribes there are, so they want the number of fragments to be as large as possible.

Find the maximum number of fragments the chain can be cut into without breaking these rules.

The only line of input contains a non-empty string $s$ consisting of lowercase English letters. The length of $s$ does not exceed $5 \cdot 10^6$.

Print one number, the maximum number of fragments the explorers can cut the chain into without violating any of the rules.

In the first case, the explorers can split the chain abbabbbab into the fragments abb, abb, and bab. Each tribe head then gets one glass piece of type a and two glass pieces of type b.

In the second case, the chain cannot be divided into more than one fragment.