Bobo 有一个只包含数字 $0$, $1$, $2$ 的，长度为 $n$ 的字符串 $s_1 \dots s_n$。他想选出最多的互不重叠的连续子串，这些子串都是 $2020$. 求最多可以选出的子串数量。

形式化地，他想要求出最大的 $k$, 使得存在 $k$ 个下标 $i_1, \dots, i_k$ 满足

• $s_{i_t} s_{i_t + 1} s_{i_t + 2} s_{i_t + 3} = 2020$
• 对于 $1 \leq t < k$, 满足 $i_t + 4 \leq i_{t + 1}$

Input

输入文件包含多组数据，请处理到文件结束。

每组数据的第一行包含一个整数 $n$，第二行包含一个字符串 $s_1 \dots s_n$.

• $1 \leq n \leq 10^5$
• $s_i \in \{0, 1, 2\}$
• $n$ 的和不超过 $10^6$.

Output

对于每组数据，输出一个整数，表示所求的值。

样例输入

4
2020
6
202020
10
1202012020

样例输出

1
1
2