382. CB Number Count

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 to define a CB Number:

For example, in the string **4991**, both **499** and **991** are CB Numbers, but Deepak can only choose either **499** or **991**, not both. - Additionally, the CB Number formed can only be a substring of the given string.

For example, in the string **481**, Deepak 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, so he needs your help in solving Gautam's challenge.

**1.**CB Numbers cannot be 0 or 1.**2.**CB Numbers include the prime numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.**3.**Any number that is not divisible by the prime numbers mentioned in point 2 is also considered a CB Number. Deepak expresses his love 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 detected, it should not be a substring or superstring of any other CB Number.For example, in the string **4991**, both **499** and **991** are CB Numbers, but Deepak can only choose either **499** or **991**, not both. - Additionally, the CB Number formed can only be a substring of the given string.

For example, in the string **481**, Deepak 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, so he needs your help in solving 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