The new girl in school Shikanoko is a bit weird, she has deer antlers and loves to eat deer cookies! Her friend Koshi has found out that the store next to the school has started selling packages of human and deer cookies. All packages have the same number of cookies, and both the human and deer cookies in the same order. A package can be expressed as a binary string where $$$1$$$ represents a deer cookie, and $$$0$$$ represents a human cookie, so for example $$$1101$$$ means the first and second cookie in the package will be deer cookies, and the third will be a human cookie.

Shikanoko wants Koshi to share a package with her, and she will be happy if she eats all of the deer cookies, and Koshi eats all the human cookies. She also wants, that at any moment, she has eaten at least the same number of cookies as Koshi.

Koshi, doesn't want to look violent, so she will only grab cookies from either ends of the packages. For example, Koshi won't eat or give the third cookie to Shikanoko if neither the second nor the fourth cookie has been eaten before.

Koshi knows she'll have to do this daily, so she has decided to try and pick a different order in which the cookies are eaten each day. An order is considered different than another if for at least two different cookies $$$i$$$ and $$$j$$$, the cookie $$$i$$$ is eaten before cookie $$$j$$$ in one order, and in the other cookie $$$j$$$ is eaten before cookie $$$i$$$.

Koshi will be bored the day that the order in which cookies are eaten has been repeated in another day before. Find the maximum possible day in which Koshi will be bored for the first time.