ARHITEKT

문제

The architect Mirko has given his three-year old son, Mirko, Jr., the task of creating the floor plan for the building he is currently working on. 

The surface he will be working on is a huge piece of paper modeled by a coordinate plane, on which all points with integer coordinates are marked. Mirko, Jr. draws the floor plan by putting his pencil in the origin and making N fast and clumsy strokes. In each stroke, he moves the pencil (without lifting it off the surface) straight to one of the 8 neighbouring points (horizontally, vertically or diagonally). The possible strokes are numbered 0 to 7 as shown in the image below. 

[이미지 1]

The 8 possible moves.

After several thousand strokes, Mirko, Jr. finally gets tired after which his father attempts to count the number of rooms in the floor plan. A room is an empty space in the floor plan, surrounded by pencil strokes on all sides. Note that it is possible for rooms to have "holes" i.e. to completely surround other rooms. Also, it is possible for that Mirko, Jr. draws the same wall segment more than once. 

Write a program that, given the exact pencil strokes, calculates the number of rooms in the floor plan. 

입력

The first line contains an integer N (1 ≤ N ≤ 100000), the number of pencil strokes. 

The second line contains a string of N digits between 0 and 7, the pencil strokes in order in which Mirko, Jr. makes them. 

출력

Output the number of rooms in the floor plan.