Lines
A string composed solely of uppercase and lowercase Latin letters is provided. You can perform the following operations on the string an unlimited number of times:
Select the entire string.
Swap the left and right halves of the selected part if its length is even.
Swap the left and right sections around the central character of the selected part if its length is odd.
Select only the right half of the selected part if its length is even.
Select only the left half of the selected part if its length is even.
Select only the right section from the central character of the selected part if its length is odd.
Select only the left section from the central character of the selected part if its length is odd.
Perform any of the above actions on the selected part of the string.
Clearly, if the selected part has an odd length, the central character remains unchanged. Additionally, if the selected part consists entirely of identical characters, it remains unchanged.
For instance, the string "baCa" can be transformed in the following ways:
"baCa" -> "Caba" -> "Caab",
or like this:
"baCa" -> "baaC"...
Similarly, the string "dbdCd" can be transformed as follows:
"dbdCd" -> "bddCd" -> "Cddbd" -> "Cdddb",
or like this:
"dbdCd" -> "bddCd" -> "bdddC"…
The task is to find the length of the longest contiguous substring composed solely of the specified character, which can be achieved by transforming the given string using the described operations.
Input
The input consists of two lines. The first line contains the target character, and the second line contains the given string. The length of the string is at least 1 and does not exceed 100000.
Output
The output should be a single number, representing the solution to the problem.