背景

小周同学苦恼于模意义下的分数计算，这种计算一般出现在求概率或者期望的题目当中。

然而，当 $3$ 个及以上的 $10^9$ 量级的数相乘时，得到的结果极有可能会发生数据溢出。

因此，我们需要先对两个数的乘积进行取模，再进行下一步运算。

为了让小周同学再也不犯这样的毛病，哈吉晨决定出一道题目，让小周同学以此为戒，不再犯这种类型的问题。

题目描述

题目的具体内容是这样的:

给定一个字符串 $S$,只包含阿拉伯数字( $0$ ~ $9$ )，乘法符号 '$*$' 和大写字母 $M$,这个字符串是由一个只包含乘法和求余两种运算的式子转换过来的，$M$表示对$10 ^9$ 取模。

你需要做的是为这个式子中添加 $M$(注意，$M$ 不能放在两个数字之间，也不能放在 '$*$' 后面)，使得式子不会出现数据溢出的情况且最后的结果的位数不能超过 $9$，你需要回答最少需要添加的 $M$ 的数量。

为了简便这个过程,我们只讨论数的位数长度 例如"$1132*13230$", $1132$ 是 $4$ 位数,$13230$是 $5$ 位数,那么该式得到的新数的位数,我们看成$4 + 5 = 9$ 位数。

当某个数位数为 $10$ 及其以上时,如果在其末尾添加一个 $M$,最后得到的值的位数应为 $9$;

若位数小于 $10$，则不发生变化。

当数的位数大于 $18$ 时,我们认为此时出现了数据溢出的情况。

格式

输入

第一行一个整数 $n (1 \le n \le 10^6)$,代表字符串的长度。

第二行一个长度为 $n$ 字符串。保证给出的字符串符合上述规则,连续的数字数量不超过 $9$。

输出

输出一个整数,代表你添加的 $M$ 的数量。

样例

28
100000*100232*234248843M*100

2

14
114514*1919810

1