// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"YES"<<"\n"
#define no cout<<"NO"<<"\n"

// Rolling Hash
// long long にして使うこと
class RHash{
	public:
	int n;
	vi base,mo;//mod
	vvi hash;
	vvi po;//pow
	
	RHash(string s){
		base={1009,9973};
		mo={1000000007,1000000009};
		
		n=s.size();
		hash=vvi(n+1,vi(2));
		po=vvi(n+1,vi(2,1));
		
		rep(i,n)rep(j,2){
			hash[i+1][j]=(hash[i][j]+s[i])*base[j]%mo[j];
			po[i+1][j]=po[i][j]*base[j]%mo[j];
		}
	}
	pii get(int l,int r){// [l,r)
		Def t[2];
		rep(i,2)t[i]=((hash[r][i]-hash[l][i]*po[r-l][i])%mo[i]+mo[i])%mo[i];
		return {t[0],t[1]};
	}
};

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin>>n;
	string s;
	cin>>s;
	string rs=s;
	reverse(all(rs));
	RHash rh(s),rh1(rs);
	loop(i,2,n+1){
		bool h=true;
		pii p1=rh.get(0,i),p2=rh1.get(n-i,n);
		bool w=0;
		for(int j=0;j<n;j+=i-1){
			if(j+i>n){
				int c=n-j;
				if(!w){
					if(rh.get(0,c)!=rh.get(j,j+c))h=false;
				}else{
					if(rh1.get(n-i,n-i+c)!=rh.get(j,j+c))h=false;
				}
				break;
			}
			if(!w){
				if(p1!=rh.get(j,j+i)){h=false;break;}
			}else{
				if(p2!=rh.get(j,j+i)){h=false;break;}
			}
			w^=1;
		}
		if(h){
			cout<<i<<endl;
			return 0;
		}
	}
}







### Prompt

Please formulate 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
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"YES"<<"\n"
#define no cout<<"NO"<<"\n"

// Rolling Hash
// long long にして使うこと
class RHash{
	public:
	int n;
	vi base,mo;//mod
	vvi hash;
	vvi po;//pow
	
	RHash(string s){
		base={1009,9973};
		mo={1000000007,1000000009};
		
		n=s.size();
		hash=vvi(n+1,vi(2));
		po=vvi(n+1,vi(2,1));
		
		rep(i,n)rep(j,2){
			hash[i+1][j]=(hash[i][j]+s[i])*base[j]%mo[j];
			po[i+1][j]=po[i][j]*base[j]%mo[j];
		}
	}
	pii get(int l,int r){// [l,r)
		Def t[2];
		rep(i,2)t[i]=((hash[r][i]-hash[l][i]*po[r-l][i])%mo[i]+mo[i])%mo[i];
		return {t[0],t[1]};
	}
};

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin>>n;
	string s;
	cin>>s;
	string rs=s;
	reverse(all(rs));
	RHash rh(s),rh1(rs);
	loop(i,2,n+1){
		bool h=true;
		pii p1=rh.get(0,i),p2=rh1.get(n-i,n);
		bool w=0;
		for(int j=0;j<n;j+=i-1){
			if(j+i>n){
				int c=n-j;
				if(!w){
					if(rh.get(0,c)!=rh.get(j,j+c))h=false;
				}else{
					if(rh1.get(n-i,n-i+c)!=rh.get(j,j+c))h=false;
				}
				break;
			}
			if(!w){
				if(p1!=rh.get(j,j+i)){h=false;break;}
			}else{
				if(p2!=rh.get(j,j+i)){h=false;break;}
			}
			w^=1;
		}
		if(h){
			cout<<i<<endl;
			return 0;
		}
	}
}







```