A lighthouse keeper spent one foggy night firing signal flares in a strict sequence and wrote down the color of every flare as a single lowercase letter, producing one continuous log string. Two flares that share the same color form an echo pair. For an echo pair, the echo gap is the number of flares fired strictly between the two matching flares (the two matching flares themselves are not counted). Your job is to scan the whole log and report the largest echo gap over every possible echo pair of matching colors. If every color in the log was fired at most once, no echo pair exists, and you must report -1 instead.

Input format

A single line containing the log string s.

Output format

A single integer: the maximum echo gap over all echo pairs, or -1 if no color repeats.

Constraints

• 1 <= length of s <= 100000
• s consists only of lowercase English letters ('a'-'z').

abca

2

cbzxy

-1