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 C {
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String letters = sc.nextLine();
	int[] maxis = new int[26];
	int[] lastseen = new int[26];
	for (int i = 0; i < 26;i++){
		lastseen[i] = -1;
		maxis[i] = -1;
		
	}
	for (int i = 0;i < letters.length();i++){
		char p = letters.charAt(i);
		int subdiff = i-lastseen[p-97];
		maxis[p-97] = Math.max(maxis[p-97], subdiff);
		lastseen[p-97] = i;
		
	}
	int i = letters.length();
	int min = 100000000;
	for (int c = 0;c < 26;c++){
		int subdiff = i-lastseen[c];
		maxis[c] = Math.max(maxis[c], subdiff);
		lastseen[c] = i;
		min = Math.min(maxis[c], min);
	}
	
	
	System.out.println(min);
}
}
