A. Alaric Magic Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Once upon a time, in the mystical land of Numeria, there was a young wizard named Alaric. Alaric possessed a powerful ability to manipulate numbers and was known for his expertise in partitioning them in unique ways. One day, Alaric stumbled upon a mystical artifact that contained a number of immense magnitude.

This number, denoted as $$$N$$$, was no ordinary number. It consisted of $$$K$$$ digits and emanated a mysterious energy. Intrigued by this peculiar number, Alaric sought to unlock its secrets by partitioning it.

However, Alaric could only create non-overlapping partitions from $$$N$$$, and each partition had to satisfy one of two magical properties: it had to either be a prime number or a perfect square. The remaining digits that were not used in any partition were deemed insignificant and were ignored.

Alaric's goal was to determine the maximum number of non-overlapping partitions he could create from $$$N$$$ while adhering to the magical properties.

Can you assist Alaric in this enchanting task?

Input

The input consists of two lines:

The first line contains an integer $$$K$$$ $$$(1 \leq K \leq 10^6)$$$, representing the number of digits in $$$N$$$. The second line contains a string $$$N$$$ consisting of $$$K$$$ digits.

Output

Output a single integer, representing the maximum number of non-overlapping partitions that can be obtained from $$$N$$$.

Examples
Input
3
687
Output
1
Input
5
10067
Output
2
Input
2
52
Output
2