1D minesweeper is a game played on a ~1 \times n~ grid, where players try to find the location of all the hidden "mines". Each grid cell contains one of the following:

• A dot (.), indicating that the cell is empty and has 0 adjacent mines.
• A digit (X), indicating that the cell is empty and has exactly X adjacent mines.
• A hash (#), indicating that the cell contains a mine.
• A question mark (?), indicating that the contents of the cell are unknown.

Given a 1D minesweeper board, what is the minimum number of mines it can contain?

Input

The first line contains a single integer ~n~ (~1 \leq n \leq 10^5~), the number of cells in the 1D minesweeper board.

The second line contains a single string ~S~ (~|S| = n~) the state of the 1D minesweeper board. The board only contains the above characters, and is always a valid game state (e.g. you cannot have #1#, as the 1 would be incorrect).

Output

Output the minimum number of mines that can be on the 1D minesweeper board with the state given.

Example

Input 1

10
.1??1?2#1.

Output 1

3

The mines can be placed in the 1D minesweeper board as shown below:

Input 2

11
.1?1.?1..1?

Output 2

3

Input 3

10
?1.1?2?2?.

Output 3

4