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
import sys
import string

def main():
    s = raw_input()
    
    res = 10**9
    for ch in string.ascii_lowercase:
	ar = [index + 1 for index, val in enumerate(s) if val == ch]
	ar = [0] + ar + [len(s) + 1]
	res = min(res, max(abs(x - y) for x, y in zip(ar, ar[1:])))
	
    print res
    
if __name__ == '__main__':
    main() 
    
