시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 305 66 41 24.118%

문제

상근이는 자기가 살 집을 설계하려고 한다.

먼저, 정수 좌표마다 점이 찍혀 있는 매우 큰 종이가 필요하다. 그 다음, 이 종이의 원점에 연필을 올린다. 이제 연필을 빠르게 N번 움직여 평면도를 그린다. 연필은 절대로 종이에서 떼지 않는다. 또, 상근이는 연필을 현재 있는 점과 인접한 8개 점 중 하나로만 이동할 수 있다. (가로, 세로, 대각선) 가능한 이동은 아래 그림과 같으며, 숫자로 나타낼 수 있다.

상근이가 그린 평면도가 주어진다. 이 때, 방의 수를 구하는 프로그램을 작성하시오. 방은 평면도 상에서 빈 공간이며, 연필 선으로 모든 면이 둘러 쌓여 있어야 한다. 방은 다른 방으로 둘러 쌓여질 수도 있다. 상근이는 이미 그었던 선을 또 그릴 수도 있다.

입력

첫째 줄에 연필을 움직인 횟수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 연필을 움직인 순서가 주어진다. 이 순서는 길이가 N인 숫자이며 0부터 7까지로 이루어져 있다. 

출력

첫재 줄에 평면도의 방의 개수를 출력한다. 

예제 입력

19
6664442220001655360

예제 출력

3

힌트

예제를 그림으로 그리면 위와 같다