Bobo has a string $s_1 \dots s_n$ of length $n$ consisting only of the digits $0$, $1$, and $2$. He wants to select the maximum number of non-overlapping contiguous substrings that are equal to $2020$. Find the maximum number of such substrings that can be selected.

Formally, he wants to find the maximum $k$ such that there exist $k$ indices $i_1, \dots, i_k$ satisfying:

• $s_{i_t} s_{i_t + 1} s_{i_t + 2} s_{i_t + 3} = 2020$
• For $1 \leq t < k$, $i_t + 4 \leq i_{t + 1}$ holds.

Input

The input contains multiple test cases. Process until the end of the file.

Each test case consists of two lines: the first line contains an integer $n$, and the second line contains a string $s_1 \dots s_n$.

• $1 \leq n \leq 10^5$
• $s_i \in \{0, 1, 2\}$
• The sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output an integer representing the required value.

Examples

Input 1

4
2020
6
202020
10
1202012020

Output 1

1
1
2