Chef loves games! But he likes to invent his own. Now he plays game "Digit Jump". Chef has sequence of digits S1, S2,..., SN,. He is staying in the first digit (S1) and want to reach the last digit (SN) in the minimal number of jumps. 
While staying in some digit x with index i (digit Si) Chef can jump into digits with indices i - 1 (Si-1) and i + 1 (Si+1) but he can't jump out from sequence. Or he can jump into any digit with the same value x. 
Help Chef to find the minimal number of jumps he need to reach digit SN from digit S1. 
 

Input
Input contains a single line consist of string S of length N- the sequence of digits.
 

Output
In a single line print single integer - the minimal number of jumps he needs.
 

Constraints

1 ≤ N ≤ 10^5
Each symbol of S is a digit from 0 to 9. 

 

Example
Input:
01234567890

Output:
1

Input:
012134444444443

Output:
4

 

Explanation
In the first case Chef can directly jump from the first digit (it is 0) to the last (as it is also 0).
In the second case Chef should jump in such sequence (the number of digits from 1: 1-2-4-5-15).
"""http://www.codechef.com/problems/
Shortest path algorithm [x]
Dynamic programming
"""

import sys
from collections import deque

inf = int(pow(2,63) - 1)

def digdump(digits):
    digits = convert(digits)
    dtable = [inf,] * 10
    dist = [inf,] * len(digits)
    dist[0] = 0
    dtable[digits[0]] = 0
    for i in xrange(1, len(digits)):
        d = digits[i]
        prev_cost = dist[i-1]
        if prev_cost < dtable[d]:
            dist[i] = prev_cost + 1
            if d == digits[i-1]:
                dtable[d] = prev_cost
            else:
                dtable[d] = prev_cost + 1
        else:
            dist[i] = dtable[d] + 1
        # print dist[i], dtable[d]
        # fix prev cost by step back
        if prev_cost > dist[i] + 1:
            dist[i-1] = dist[i] + 1
            if dist[i-1] < dtable[digits[i-1]]:
                dtable[digits[i-1]] = dist[i-1] 
            #print 'back', i, dist[i-1], d, prev_cost
    # print dist, dtable
    return dist[-1]

 
def convert(line):
    return [int(i) for i in line]
 

def debug_dtab(group):
    for i, v in enumerate(group):
        print len(v)


def digjump_bfs(digits):
    visited_digits.clear()
    visited = set()
    parent = [None,] * len(digits)
    queue = deque()
    tab = build_group(digits)
    #debug_dtab(tab)
    queue.append(0)
    visited.add(0)
    while queue:
        node = queue.pop()
        # print 'node', node
        for child in gen_children(digits, tab, node, parent):
            if child not in visited:
                visited.add(child)
                # print 'c', child
                parent[child] = node
                queue.appendleft(child)
    # Trace back
    n = len(digits) - 1
    count = 0
    while n != 0:
        n = parent[n]
        count += 1
    return count

visited_digits = set()

def gen_children(digits, tab, i, parent):
    if i > 0:
        yield i - 1
    if i < len(digits) - 1:
        yield i + 1
    d = digits[i]
    if d not in visited_digits:
        visited_digits.add(d)
    else:
        return
    # if parent[i] is not None and digits[parent[i]] == digits[i]:
    #     return
    for j in tab[d]:
        if j not in (i, i-1, i+1):
            yield j


def build_group(digits):
    tab = []
    for i in range(10):
        tab.append(set())
    for i, d in enumerate(digits):
        tab[d].add(i)
    return tab


def test():
    # test_func = digdump
    test_func = digjump_bfs
    print test_func(convert('0'))
    print test_func(convert('101'))
    # print test_func(convert('0121344444434443'))
    # print test_func(convert('01234567890'))
    # print test_func(convert('0123410193837418926571657382471036517356173084'))
    print test_func(convert('0998887776665554443322223300885577'))
    print test_func(convert('099887730085577'))
#    '''
    import random
    digits = []
    for i in xrange(pow(10, 6)):
        digits.append(random.randint(0, 9))
    print 'starting..'
    print test_func(digits)
#    '''

def main():
    line = raw_input().strip()
    print digjump_bfs(convert(line))
 
 
main()
#test()