题目描述

JAG 王国中有 (n) 只史莱姆排成一列。初始时，从左到右第 (i) 只史莱姆的等级为 (L_i)。

你可以对相邻且等级相同的两只史莱姆施放合成魔法，将它们合成为一只等级 (X+1) 的史莱姆。合成后的史莱姆出现在原两只史莱姆位置的中间。史莱姆不能自行移动，也不能被移动。

若当前不存在相邻同等级史莱姆，则无法施放魔法。

请问以最优顺序施放魔法时，最多可以施放多少次，也就是最多能减少多少只史莱姆。

输入中的等级只有 (0) 到 (9)，但合成后可能出现 (10) 及以上等级。

输入格式

输入包含多个数据集，数据集个数不超过 (40)。

每个数据集格式如下：

n
L

(1\le n\le 2\times 10^5)。(L) 为长度 (n) 的数字串，第 (i) 位表示 (L_i)。

输入以单独一行 0 结束。

输出格式

对每个数据集，输出最多施放魔法次数。

样例输入

4
1111
5
31132
10
3331124331
0

样例输出

3
1
8