col = { 
    7 => 1,
    4 => 1,
    1 => 1,
    8 => 2,
    2 => 2,
    9 => 3,
    6 => 3,
    3 => 3,
}

loop do
    seq = gets.chomp.split("").map(&:to_i)
    break if seq == [0] 
    hash = {}
    ((1..9).to_a - [5]).permutation(2) do |i, j|
        next if col[i] > col[j]
        hash[[i, j, nil]] = 0 
    end 

    seq.each do |k| 
        hash2 = Hash.new(Float::INFINITY)
        hash.each do |(i, j, prev_foot), v|
            if col[k] <= col[j]
                v2 = (prev_foot == :left ? v + 1 : v)
                key = [k, j, :left]
                hash2[key] = v2 if v2 < hash2[key]
            end
            if col[i] <= col[k]
                v2 = (prev_foot == :right ? v + 1 : v)
                key = [i, k, :right]
                hash2[key] = v2 if v2 < hash2[key]
            end
        end
        hash = hash2
    end 
    p hash.values.min
end