After the Pharaoh Maged was laid to rest, his soul faced the trials of the Egyptian underworld. The Pharaoh had no fear, as he believed in his most trusted advisor, the Wizard Rishi, to guide him to the afterlife.

Unbeknownst to the Pharaoh, Rishi had been too busy singing karaoke, neglecting his wizardly duties and had forgotten to conduct any of the rituals required to ensure the safe passage of Maged's soul. In a desperate attempt to save his Pharaoh, the wizard opens up the Book of the Dead, trying to find the spell passage with the greatest magical power.

The Book of the Dead contains a single string of spells, where each spell is represented as a letter in the archaic language known as English. A valid passage is contiguous substring with no duplicate spells. All spells are equally powerful, so the strength of a passage is measured solely by its length.

Input

The input consists of a singular string ~s~ (~1 \leq s \leq 10^6~), representing the passage in the Book of the Dead. It is guaranteed that ~s~ consists only of lowercase English letters.

Output

Output a single integer representing the greatest power of a valid passage Rishi can chant to save his Pharaoh, i.e. the length of the largest substring of the passage that contains no duplicate characters.

Example

Input 1

ancientegypt

The longest valid passage is 'ntegyp', with a length of 6.

Output 1

6

Input 2

thewizardrishiandthepharaohmaged

Output 2

9