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
s=readline()
res=s.length
if (res%2==0)
{
    res/=2
    ++res
}
else
{
    ++res
    res/=2
}

function max(a,b)
{
    return a+b-min(a,b)
}

function min(a,b)
{
    if (a<b)return a;
    return b
}

function go(c)
{
    last=-1
    re=0
    for (i=0;i<s.length;i++)
    {
        if (s[i]==c)
        {
            re=max(re,i-last);
            last=i
        }
    }
    re=max(s.length-last,re)
    //print(re)
    res=min(res,re)
}
go('q');go('w');go('e');
go('r');go('s');go('z');
go('t');go('d');go('x');
go('y');go('f');go('c');
go('u');go('g');go('v');
go('i');go('h');go('b');
go('o');go('j');go('n');
go('p');go('k');go('m');
go('a');go('l');
print(res)