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
from collections import defaultdict

s = input()

if len(set(s)) == 1:
    print(1)
elif len(set(s)) == len(s):
    print((len(s) // 2) + 1)
else:
    dist = defaultdict(lambda: (0, 0))
    for i, c in enumerate(s):
        if dist[c] == (0, 0):
            dist[c] = (i, i+1)
        else:
            dist[c] = (i, max(i - dist[c][0], dist[c][1]))
    
    m = float('inf')
    for k in dist:
        dist[k] = (dist[k][0], max(dist[k][1], len(s) - dist[k][0]))
        if dist[k][1] > float('-inf'):
            m = min(m, dist[k][1])

    print(m)