1090 : 2020

Description

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

形式化地，他想要求出最大的 k, 使得存在 k 个下标 i₁, …, i_k 满足

• s_its_it + 1s_it + 2s_it + 3 = 2020
• 对于 1 ≤ t < k, 满足 i_t + 4 ≤ i_t + 1 

Input

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

每组数据的第一行包含一个整数 n，第二行包含一个字符串 s₁…s_n.

• 1 ≤ n ≤ 10⁵
• s_i ∈ {0, 1, 2}
• n 的和不超过 10⁶.

Output

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

Sample

4
2020
6
202020
10
1202012020

1
1
2

Hint

Source

Author

ftiasch