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:

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.

**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

Loading...

View Submissions

Console