题目描述

教学楼走廊的顶上挂着一排彩灯，一共 $n$ 盏，从左到右排成一条线。每盏灯亮三种颜色中的一种，三种颜色分别记作 $0$、$1$、$2$。这批灯的线路接得有点随意，同一排里什么颜色都有。程老师每次路过都要抬头看一眼，越看越觉得别扭，打算把它们调成清一色的——最后整排灯亮同一种颜色。

调灯的开关是分组控制的。每按一次开关，可以选中一段连续排列的灯，前提是这一段里每一盏灯的颜色都相同，然后这一段灯会一起变成另外两种颜色中的一种。被选中的这一段只要求段内各灯颜色相同，不要求它是同色灯所能连成的最大一段：一段同色灯里任意截取一小截，截出来的这一小截也算合法的一段。一次开关只作用于选中的这一段，段外的灯不受影响。

程老师想把开关按得尽量少。请你算一算：给定这一排灯一开始各自是什么颜色，最少按几次开关，就能让整排灯变成同一种颜色。可以证明，一直按下去总能做到。

输入格式

从文件 lamp.in 中读入数据。

第一行一个正整数 $n$，表示灯的盏数。

第二行一个长度为 $n$ 的字符串，只由字符 0、1、2 组成，依次表示从左到右每一盏灯的颜色。

输出格式

输出到文件 lamp.out 中。

一行一个整数，表示让整排灯变成同一种颜色所需的最少开关次数。

数据范围

对于所有测试数据，保证：$1 \le n \le 12$，字符串中只出现字符 0、1、2。

特殊性质 A：一开始只出现两种颜色。

特殊性质 B：一开始所有灯的颜色都相同。

4
0101

2

3
001

1

样例解释

样例 1：一开始是 0101。第一盏灯的颜色是 $0$，同色且连续的一段只有它自己这一盏，把它变成 $1$，整排变成 1101；此时左边两盏都是 $1$，可以一起选中，把这两盏变成 $0$，整排变成 0001；再把最后那一盏单独变成 $0$，整排变成清一色 0000。这样用三次。

上面这个走法不是最省的。把第二盏灯（颜色 $1$）单独选中改成 $0$，整排变成 0001；此时前三盏颜色都是 $0$，可以一次选中，一起改成 $1$，整排变成 1111。两次就够了。而一次是不够的：一排 0101 里任意一段同色灯都只有一盏，按一次开关至多让一盏灯换个颜色，另外三盏里必然还有别的颜色。

样例 2：前两盏灯颜色都是 $0$，可以一次选中并一起改成 $1$，整排变成 111，所以一次就够。