You are given a string s of lowercase English letters. Perform the following operation exactly once:

• Choose one lowercase English letter and delete all of its occurrences from s. Choosing a letter that does not appear in s leaves the string unchanged.

After the deletion, partition the remaining string into contiguous non-empty segments such that no letter appears more than once within any segment. Choose the deleted letter that minimizes the number of segments in an optimal partition. Return that minimum number of segments.

If the deletion leaves the string empty, the answer is 0.

Examples

Example 1

Input: s = "abcccde"
Output: 1
Explanation: Deleting 'c' leaves "abde", which has no repeated letter, so a single segment suffices.

Example 2

Input: s = "abdaa"
Output: 1
Explanation: Deleting 'a' leaves "bd", a single segment with no repeats.

Example 3

Input: s = "aaaaa"
Output: 0
Explanation: Deleting 'a' leaves the empty string, which needs 0 segments.