#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


vector<int> manacher(string s){
  int n=s.size();
  vector<int> v(n);
  for(int i=0,j=0;i<n;){
    while(i-j>=0&&i+j<n&&s[i-j]==s[i+j]) j++;
    v[i]=j;
    int k=1;
    while(i-k>=0&&i+k<n&&k+v[i-k]<j) v[i+k]=v[i-k],k++;
    i+=k;j-=k;
  }
  return v;
}


template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}

//INSERT ABOVE HERE
signed main(){
  int n;
  cin>>n;
  string t;
  cin>>t;
  auto ms=manacher(t);

  for(int l=2;l<=n;l++){
    int flg=1;
    for(int i=l-1;i<n;i+=l-1)
      flg&=ms[i]==min(i+1,n-i);
    if(flg) drop(l);
  }

  assert(0);
  return 0;
}


### Prompt

Your challenge is to write a Cpp solution to the following problem:

E: Round-trip String

story

This is the world where all human beings have become competition programmers. In this world, there are many customs that you cannot think of in the present age. One of them is the custom of sending a character string when expressing gratitude to parents, especially mothers. There are regional differences in what kind of character string is suitable for sending, but in the northern land of Hokkaido, the simplest possible character string is suitable as a gift. Also, the sending mother needs to answer to the child how beautiful the sent string is in return.

Now you are being consulted by the mother of one child. The mother got a nice string from her child, but she can't really measure how great it is. According to the custom of Hokkaido, the character string T to be sent to the mother is made by reciprocating a certain character string S. At this time, if S is the shortest possible string, it is a better string T. The mother rewards her child for her hard work, so she wants to find the shortest string that can make a T, but that's difficult. I want you to make full use of your programming ability to solve your mother's worries.

problem

From a string S of length 2 or more, generate a string T of length N according to the following rules. Here, let K be the string length of S, and T [i] represents the i-th character of the string T. Here, the first character of T is the 0th character.

T [i] = S [K -1 --| (i $ \ bmod $ (2K -2)) --K + 1 |]

Given only T, there can be multiple strings that produce T. Output the smallest string length K_ {min} among those strings.

Input format


N
T


Constraint

* 2 \ leq N = | T | \ leq 1,000,000
* String consists of lowercase letters only



Output format

Output the length K_ {min} of the shortest string S that produces T.

Input example 1


6
tabata


Output example 1


3

There are three possible possibilities: `tabata`,` tabat`, and `tab`, but the answer is 3 because` tab` is the shortest.

Input example 2


Four
hcpc


Output example 2


3

Input example 3


60
aaaaaabbbbbbbbbbbaaaaaaaaaaabbbbbbbbbbbaaaaaaaaaaabbbbbbbbbb


Output example 3


12





Example

Input

6
tabata


Output

3

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


vector<int> manacher(string s){
  int n=s.size();
  vector<int> v(n);
  for(int i=0,j=0;i<n;){
    while(i-j>=0&&i+j<n&&s[i-j]==s[i+j]) j++;
    v[i]=j;
    int k=1;
    while(i-k>=0&&i+k<n&&k+v[i-k]<j) v[i+k]=v[i-k],k++;
    i+=k;j-=k;
  }
  return v;
}


template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}

//INSERT ABOVE HERE
signed main(){
  int n;
  cin>>n;
  string t;
  cin>>t;
  auto ms=manacher(t);

  for(int l=2;l<=n;l++){
    int flg=1;
    for(int i=l-1;i<n;i+=l-1)
      flg&=ms[i]==min(i+1,n-i);
    if(flg) drop(l);
  }

  assert(0);
  return 0;
}


```