#include<stdio.h>
#include<string.h>
# define max 1000002
char a[100005];
long long int jump[100005];
int status[10]={0};
long long int indx;
void editarray(long long int n)
{ long long int i,j,a1,b,b1;
j=indx+1;
//printf("%d",j);
int c=10;
while(j<n)
{ for(i=indx+1;i<n;i++)
{ a1=a[i]-'0';
b1=a[indx]-'0';
if(a1==b1)
break;
}
if(i==n)
{ for(j=indx+1;j<i;j++)
{ if(jump[j]>jump[indx]+j-indx)
jump[j]=jump[indx]+j-indx;
}
break;
}
else
{ for(j=indx+1;j<i;j++)
{ a1=jump[indx]+j-indx;
b=jump[i]+i-j;
if(jump[j]>a1)
jump[j]=a1;
if(jump[j]>b)
jump[j]=b;
}
}
indx=i;
}
}
int finddistinct(long long int n)
{ int a1;
long long int i;
for(i=0;i<n;i++)
{ a1=a[i]-'0';
if(status[a1]==0)
{ a1=a[i]-'0';
indx=i;
// printf("%lld ",i);
status[a1]=1;
return a1;
}
}
return -1;
}
long long int caldistinct(long long int n,long long int x)
{ long long int min=max;
long long int temp,i;
if(x==a[0]-'0')
return 0;
for(i=0;i<n;i++)
{ if(i==indx)
continue;
if(i<indx)
temp=indx-i;
else
temp=i-indx;
if(jump[i]+temp<min)
min=jump[i]+temp;
}
return min;
}
long long int caljump()
{ long long int a1,c,i,n,min,d,e;
int b,temp,b1;
for(i=0;i<n;i++)
jump[i]=1000000;
char *s=a;
a1=*s-'0';
if(a[n-1]==a[0])
return 1;
int count =10;
while(count--)
{ temp=0;
b=finddistinct(n);
if(b<0)
return;
a1=caldistinct(n,b);
c=a[n-1]-'0';
min=max;
for(i=0;i<n;i++)
{b1=a[i]-'0';
if(b1==b&&jump[i]<min)
min=jump[i];
if(b1==b&&temp==1)
{ if(jump[i]>a1+1)
jump[i]=a1+1;
// printf("%d ",b1);
}
if(b1==b&&!temp)
{ if(jump[i]>a1);
{ jump[i]=a1;
temp=1;
}
}
}
for(i=0;i<n;i++)
{b1=a[i]-'0';
if(b1==b&&jump[i]>min)
{ // printf("%lld %d ",i,b);
jump[i]=min+1;
}
}
// for(d=0;c<n;d++)
// printf("%lld\n",jump[d]);
editarray(n);
}
}
int main ()
{
long long int b,c;
c=caljump();
if(c==1)
else
//for(c=0;c<b;c++)
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RyaW5nLmg+CiMgZGVmaW5lIG1heCAxMDAwMDAyCmNoYXIgYVsxMDAwMDVdOwpsb25nIGxvbmcgaW50IGp1bXBbMTAwMDA1XTsgCmludCBzdGF0dXNbMTBdPXswfTsKbG9uZyBsb25nIGludCBpbmR4Owp2b2lkIGVkaXRhcnJheShsb25nIGxvbmcgaW50IG4pCnsgbG9uZyBsb25nIGludCBpLGosYTEsYixiMTsKICBqPWluZHgrMTsKICAvL3ByaW50ZigiJWQiLGopOwogICBpbnQgYz0xMDsKICAgIHdoaWxlKGo8bikKICB7IGZvcihpPWluZHgrMTtpPG47aSsrKQogICAgIHsgYTE9YVtpXS0nMCc7CiAgICAgICBiMT1hW2luZHhdLScwJzsKICAgICAgIGlmKGExPT1iMSkgIAogICAgICAgYnJlYWs7ICAgCiAgICAgIAogICAgIH0KICAgIGlmKGk9PW4pCiAgICAgeyBmb3Ioaj1pbmR4KzE7ajxpO2orKykKICAgICAgIHsgIGlmKGp1bXBbal0+anVtcFtpbmR4XStqLWluZHgpIAogICAgICAgIGp1bXBbal09anVtcFtpbmR4XStqLWluZHg7CiAgICAgICB9CiAgICAgIGJyZWFrOwogICAgIH0KICAgZWxzZQogICB7IGZvcihqPWluZHgrMTtqPGk7aisrKSAKICAgICAgeyBhMT1qdW1wW2luZHhdK2otaW5keDsKICAgICAgICAgYj1qdW1wW2ldK2ktajsKICAgICAgICAgaWYoanVtcFtqXT5hMSkKICAgICAgICAganVtcFtqXT1hMTsKICAgICAgICAgaWYoanVtcFtqXT5iKQogICAgICAgICBqdW1wW2pdPWI7IAogICAgIH0KICAgfQogIGluZHg9aTsgCiB9IAoKfQoKaW50IGZpbmRkaXN0aW5jdChsb25nIGxvbmcgaW50IG4pCnsgIGludCBhMTsKICBsb25nIGxvbmcgaW50IGk7IAogIGZvcihpPTA7aTxuO2krKykKICAgeyBhMT1hW2ldLScwJzsKICAgIGlmKHN0YXR1c1thMV09PTApCiAgICAgeyBhMT1hW2ldLScwJzsKICAgICAgICBpbmR4PWk7CiAgICAgIC8vIHByaW50ZigiJWxsZCAiLGkpOyAKICAgICAgIHN0YXR1c1thMV09MTsKICAgICAgIHJldHVybiBhMTsKICAgICAKICAgICB9CiAgIH0KIHJldHVybiAtMTsKfQpsb25nIGxvbmcgaW50IGNhbGRpc3RpbmN0KGxvbmcgbG9uZyBpbnQgbixsb25nIGxvbmcgaW50IHgpCnsgbG9uZyBsb25nIGludCBtaW49bWF4OwogICBsb25nIGxvbmcgaW50IHRlbXAsaTsgCiAgaWYoeD09YVswXS0nMCcpCiAgcmV0dXJuIDA7CiAgZm9yKGk9MDtpPG47aSsrKSAKICAgICB7IGlmKGk9PWluZHgpCiAgICAgICAgY29udGludWU7CiAgICAgICBpZihpPGluZHgpCiAgICAgICB0ZW1wPWluZHgtaTsKICAgICAgIGVsc2UKICAgICAgIHRlbXA9aS1pbmR4OwogICAgICAgaWYoanVtcFtpXSt0ZW1wPG1pbikKICAgICAgIG1pbj1qdW1wW2ldK3RlbXA7CiAgICAgfQpyZXR1cm4gbWluOwp9CmxvbmcgbG9uZyBpbnQgY2FsanVtcCgpCnsgbG9uZyBsb25nIGludCBhMSxjLGksbixtaW4sZCxlOwogIGludCBiLHRlbXAsYjE7CiAgbj1zdHJsZW4oYSk7CiAgZm9yKGk9MDtpPG47aSsrKQogICBqdW1wW2ldPTEwMDAwMDA7CiAgY2hhciAqcz1hOwogIGExPSpzLScwJzsKICBpZihhW24tMV09PWFbMF0pCiAgcmV0dXJuIDE7CiAgaW50IGNvdW50ID0xMDsgCiAgd2hpbGUoY291bnQtLSkKICB7IHRlbXA9MDsKICAgIGI9ZmluZGRpc3RpbmN0KG4pOwogICAgaWYoYjwwKQogICAgcmV0dXJuOwogICAgYTE9Y2FsZGlzdGluY3QobixiKTsKICAgIGM9YVtuLTFdLScwJzsKICAgIG1pbj1tYXg7CiAgICBmb3IoaT0wO2k8bjtpKyspCiAgICB7YjE9YVtpXS0nMCc7CiAgICAgaWYoYjE9PWImJmp1bXBbaV08bWluKQogICAgIG1pbj1qdW1wW2ldOwogICAgIGlmKGIxPT1iJiZ0ZW1wPT0xKQogICAgeyBpZihqdW1wW2ldPmExKzEpCiAgICAgICAgIGp1bXBbaV09YTErMTsKICAgIC8vICBwcmludGYoIiVkICIsYjEpOwogICAgfQogICBpZihiMT09YiYmIXRlbXApCiAgICB7IGlmKGp1bXBbaV0+YTEpOwogICAgICB7IGp1bXBbaV09YTE7CiAgICAgICAgdGVtcD0xOwogICAgICB9ICAgCiAgICB9ICAgCiAgCiAgICB9ICAKICAgZm9yKGk9MDtpPG47aSsrKQogICAge2IxPWFbaV0tJzAnOwogICAgIGlmKGIxPT1iJiZqdW1wW2ldPm1pbikKICAgICB7IC8vIHByaW50ZigiJWxsZCAlZCAgICAgICIsaSxiKTsKICAgICAgIGp1bXBbaV09bWluKzE7CiAgICAgfSAgIAogICAgfSAKICAvLyBmb3IoZD0wO2M8bjtkKyspCiAgIC8vIHByaW50ZigiJWxsZFxuIixqdW1wW2RdKTsgCiAgIGVkaXRhcnJheShuKTsKICB9CiAKfQogaW50IG1haW4gKCkgCnsKCWxvbmcgbG9uZyAgaW50IGIsYzsKIAlzY2FuZigiJXMiLGEpOwoJYj1zdHJsZW4oYSk7CgljPWNhbGp1bXAoKTsKICAgIGlmKGM9PTEpCiAgICBwcmludGYoIjFcbiIpOwoJZWxzZQoJLy9mb3IoYz0wO2M8YjtjKyspCiAgICBwcmludGYoIiVsbGRcbiIsanVtcFtiLTFdKTsKCXJldHVybiAwOwp9