775. Counting CB Numbers

0

Medium

Deepak and Gautam are discussing a unique type of number called a Coding Blocks Number or CB Number. They have established the following criteria for defining a CB Number: 1. 0 and 1 are not considered CB numbers.
2. 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29 are considered CB numbers.
3. Any number that is not divisible by the numbers listed in point 2 (above) is also considered a CB number. Deepak expresses his fondness for CB numbers, which prompts Gautam to challenge him. Gautam will provide Deepak with a string of digits. Deepak's task is to determine the number of CB numbers in the string. - Once a CB number is identified, it should not be a substring or superset of any other CB number.
For example, in **4991**, both **499** and **991** are CB numbers, but you can only choose either **499** or **991**, not both. - Additionally, the CB number formed can only be a substring of the original string.
For example, in **481**, you cannot consider **41** as a CB number because 41 is not a substring of **481**. Since there can be multiple solutions, Gautam asks Deepak to find the maximum number of CB numbers that can be formed from the given string. Deepak needs to teach a class of Launchpad students. Help him solve Gautam's challenge.

Input Format

The first line contains the size of the string. The next line contains a string of digits.

Output Format

Output the maximum number of CB numbers that can be formed.

Example

Input

5 81615

Output

2

Constraints

1 <= Length of digit strings <= 17