You are given a string s consisting of lowercase Latin letters. Character c is called k-dominant iff each substring of s with length at least k contains this character c.

You have to find minimum k such that there exists at least one k-dominant character.

Input

The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 100000).

Output

Print one number — the minimum value of k such that there exists at least one k-dominant character.

Examples

Input

abacaba


Output

2


Input

zzzzz


Output

1


Input

abcde


Output

3
def main():
    s = input()
    lo, hi = 0, len(s)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        cnt = dict.fromkeys("abcdefghijklmnopqrstuvwxyz", 0)
        for i in range(mid):
            cnt[s[i]] += 1
        v = {c for c, x in cnt.items() if not x}
        for i, c in zip(range(mid, len(s)), s):
            cnt[s[i]] += 1
            cnt[c] -= 1
            if not cnt[c]:
                v.add(c)
                if len(v) == 26:
                    lo = mid
                    break
        else:
            hi = mid
    print(hi)


if __name__ == '__main__':
    main()
