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 java.util.Scanner;

public class C888 {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			char ar[] = sc.next().toCharArray();
			int min = Integer.MAX_VALUE;
			for (char c = 'a'; c <= 'z'; c++) {
				int cMax = Integer.MIN_VALUE;
				int p = -1;
				for (int i = 0; i < ar.length; i++) {
					if (ar[i] == c) {
						cMax = Math.max(cMax, i - p);
						p = i;
					}
				}
				cMax = Math.max(cMax, ar.length - p);
				min = Math.min(min, cMax);
			}
			System.out.println(min);
		}
	}
}
