Problem description

Paulina ma zegar, który składa się z N wyświetlaczy siedmiosegmentowych. Każdy segment, który pokazuje zegar, możemy przedstawić jako odcinek długości 1. Odległości między kolejnymi wyświetlaczami zegara to także 1.

Poniżej znajduje się przykładowy zegar dla N = 10, który wyświetla liczbę 0123456789 (Paulina nie ma nic przeciwko zerom wiodącym).

Paulina ustawiła swój zegar tak, żeby wyświetlał czas pozostały do świąt, ale zdenerwowało ją, jak duża jest ta liczba. Z tego powodu postanowiła ona zemścić się na zegarze i przeciąć go jednym prostym cięciem. Po takim cięciu niektóre cyfry mogły zostać przecięte i rozpaść się na kilka fragmentów.

Na przykład dla poniższego cięcia, cyfra 7 rozpadnie się na 3 fragmenty, cyfra 1 na 2 fragmenty, a cyfra 5 pozostanie w jednym fragmencie.

Jak wiadomo, Paulina chce zostać programistką, więc nie posiada rąk chirurga. Dlatego, cięcie przez nią wykonane na pewno nie będzie przechodziło przez żaden z końców segmentów wyświetlaczy, ani nie będzie równoległe do żadnego z segmentów.

Wartością cięcia Paulina nazywa sumaryczną liczbę fragmentów, na jakie rozpadną się cyfry wyświetlane przez zegar. Paulina chciałaby się dowiedzieć, jaka jest największa możliwa wartość cięcia, które może wykonać. Musi ona jeszcze jednak spakować prezenty, więc poprosiła Cię o pomoc w rozwiązaniu tego problemu.

Wejście

W pierwszym wierszu wyjścia znajduje się jedna liczba całkowita N - ilość cyfr, które wyświetla zegar.

W drugim wierszu znajduje się N cyfr reprezentujących liczbę aktualnie wyświetlaną przez zegar. Dopuszczalne są zera wiodące.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita - maksymalna liczba fragmentów, na którą można przeciąć liczbę wyświetlaną przez zegar.

Ograniczenia

1 ≤ N ≤ 500 000.

Przykład

3
715

9