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?
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 a single integer, representing the maximum number of non-overlapping partitions that can be obtained from $$$N$$$.
3 687
1
5 10067
2
2 52
2
Name |
---|