408730: GYM103274 H HeatWave

H. HeatWavetime limit per test8 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThermodynamics are weird man, humanity has been dealing with the same issue for centuries and still couldn't find a good way around it.Juanfra, while installing a water cooler in a computer - circa 2021.

Juanfra is a professional gamer - he plays videogames consistently every day, and sometimes he also works as a software developer in his free time. Recently, a brand new game got released: "Awesome Mar'ia Sisters" by the Noentiendo company, which some conspiracy-advocate people consider to be a disguised fresh remake of another fairly famous game about a pair of plumber brothers, but who could even believe such a thing when this game is about two construction worker sisters, right?

Anyway, Juanfra, who obviously doesn't even consider that possibility which only some out-of-mind haters can conceive, wants to play this new game, because otherwise what kind of pro gamer would he be? So he decided to upgrade his computer. He's been doing research for a long time and finally arrived to the conclusion that buying parts separately and from different brands is going to give him the best computer quality as possible.

It turned out that the Awesome Mar'ia Sisters game is so CPU demanding that Juanfra's computer started overheating after just a couple of minutes of gameplay - he couldn't even finish the tutorial steps! Unacceptable! He was so mad about it that he ran to the store and bought the first liquid nitrogen cooler he saw there, which proved to be an immediate solution to the problem. Now relaxed and proud of his computer building skills, he kept mastering the game. He was enjoying it so much that he didn't notice the heatwave that started striking the region lately. Unfortunately, the temperatures got so high that not even the cool cooler he installed could help - it got so stressed that it began vibrating due to a poor fixation to the motherboard and got a crack which made it leak nitrogen into the computer case. One night, while he was just warming up doing some blindfold speedruns of the game, the computer started displaying random colors on the screen, which Juanfra didn't notice because he was playing blindfold, so it went on like this for many hours. When he finally finished the blindfold speedrun (which was a new world record by the way), he noticed his huge blunder. However, after investigating for a while he discovered that some transistors melted in his computer components, and with a little help from the spilled nitrogen now he's got a third possible state for a bit!

He immediately figured out that now he can store more games in his computer by compressing them and he's so excited about this fact that he wants to try it right away. The first method he thought of to compress them is to choose a sequence of zeroes and ones (which we'll call $$$w$$$), and then replace it by this new bit state '2' in as many places as he can in the game file. He also needs to be able to decompress the game later in case he wants to install the game in his old conventional computer, so he should be able to replace all the occurrences of '2' with $$$w$$$ in the compressed file and get the exact original one. In addition, Juanfra would like $$$w$$$ to fit into one register of his CPU so he can run this algorithm as fast as possible. This means that $$$w$$$ can be of any length up to the size of one of his CPU registers. The thing is he doesn't remember the exact CPU he's got for his computer and he's very busy playing to look it up, he only remembers it was less than 200 bits, but it can really be any number of bits fewer than 200 because he says it's from an experimental limited-edition release by the Noentiendo company specifically tuned to run their games.

Would you help him implement his idea so he doesn't lose time and can start working on a new world record for blindfold hand-tied speedrun of Awesome Mar'ia Sisters? Juanfra even says he allows you to find out his CPU model so you can make a better work!

Input

The input will consist of two lines. The first one contains an integer $$$b$$$ ($$$0<b<200$$$) which is the number of bits that Juanfra's CPU supports. The second one contains a sequence $$$T$$$ ($$$0<|T|<10^5$$$) of characters '0' and '1' representing the file to compress.

Output

Output a line containing the minimum size that $$$T$$$ can have after performing the compression operation described in the statement using a sequence $$$w$$$ of your choice, with $$$|w| \leq b$$$.

ExamplesInput

4
11011

Output

2

Input

4
110110

Output

2

Input

4
11001100

Output

2