평면도

상근이는 자신이 살 집의 평면도를 그리려고 한다.

먼저 정수 좌표마다 점이 찍혀 있는 매우 큰 종이를 생각한다. 연필은 원점에서 시작한다. 이제 연필을 종이에서 떼지 않고 빠르게 N번 움직여 평면도를 그린다. 연필은 매번 현재 점과 인접한 8개 점 중 하나로만 이동할 수 있다. 즉, 가로, 세로, 대각선 방향으로 이동할 수 있다.

방향 번호는 현재 점 P를 기준으로 다음과 같이 배치되어 있다.

7 0 16 P 25 4 3

상근이가 그린 평면도가 주어진다. 평면도에 있는 방의 수를 구하시오. 방은 연필 선으로 경계가 완전히 둘러싸인 빈 공간이다. 방 안에 다른 방이 들어 있을 수도 있다. 연필은 이미 그었던 선을 다시 그을 수도 있다.

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

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

첫째 줄에 평면도에 있는 방의 수를 출력한다.