Byteazar 得到了一个长度为 $n$ 的字符串 $S$ ($s_1 \dots s_n$)，该字符串仅由数字 '0'、'1' 和 '2' 组成。他想要从中选出尽可能多的不相交子序列，使得每个子序列都等于 2020。

形式化地，Byteazar 想要找到 $k$ 个四元组 $(a_1, b_1, c_1, d_1), \dots, (a_k, b_k, c_k, d_k)$，满足：

• $1 \le a_i < b_i < c_i < d_i \le n$
• $s_{a_i} s_{b_i} s_{c_i} s_{d_i} = 2020$
• $\{a_i, b_i, c_i, d_i\} \cap \{a_j, b_j, c_j, d_j\} = \emptyset$，对于所有 $i \neq j$。

求 $k$ 的最大值。

输入格式

输入包含多组测试数据，以文件结束符（EOF）终止。

每组测试数据的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。第二行包含字符串 $S$ ($s_1 \dots s_n$)，其中 $s_i \in \{0, 1, 2\}$。所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个整数，表示结果。

样例

样例输入 1

4
2222
7
2101210
9
122002200

样例输出 1

0
1
2