#include "bits/stdc++.h"
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<stack>
#include<complex>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;
	
#define WHATS(var)cout<<__LINE__<<' '<<#var<<"="<<var<<endl;
	
template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){
	os << "( " << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<T> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const set<T> &v){
	int i=0;
	for(auto it:v){
		if(i > 0){os << ' ';}
		os << it;
		i++;
	} 
	return os;
}

using ll = long long int;
using ha = pair<ll, ll>;
struct RollingHash {
	static const ll mul0 = 10009, mul1 = 10007;
	static const ll add0 = 1000010007, add1 = 1003333331;
	static const ll mod0 = 1000000007, mod1 = 1000000009;

	size_t len=0;
	//vector<ll> hash_, hash2_;
	vector<ha>hash_;
	//static vector<ll> pmo_, pmo2_;
	static vector<ha>pmo_;
	void init(const vector<ll>& s) {
		hash_.resize(len+s.size()+ 1);
		hash_[0] = make_pair(0, 0);

		if (pmo_.empty()) {
			pmo_.push_back(make_pair(1, 1));
		}
		while (pmo_.size() <= len+s.size()) {
			pmo_.push_back(make_pair(pmo_.back().first*mul0%mod0, pmo_.back().second*mul1%mod1));
		}
		for (unsigned int i = 0; i < s.size(); ++i) {
			int id=i+len;
			hash_[id + 1] = make_pair((hash_[id].first * mul0 + s[i])%mod0, (hash_[id].second*mul1 + s[i])%mod1);
		}
		len += s.size();

		return;
	}
	void init(const string& s) {
		vector<ll>v;
		for (char c : s) {
			v.push_back(c);
		}
		init(v);
	}
	ha hash(const int l, const int r)const { // s[l..r]
		auto p=make_pair(hash_[r + 1].first - hash_[l].first * pmo_[r + 1 - l].first,
			hash_[r + 1].second - hash_[l].second * pmo_[r + 1 - l].second);
		
		p.first%=mod0;
		p.second%=mod1;
		if(p.first<0)p.first+=mod0;
		if(p.second<0)p.second+=mod1;

		return p;
	}
	ha  hash()const { // s[all]
		return hash(0, len - 1);
	}

	static ha concat(const ha L, const ha R, const int RLength) { // hash(L+R) 
		return make_pair((R.first + L.first*pmo_[RLength].first)%mod0, (R.second + L.second*pmo_[RLength].second)%mod1);
	}

	ha get_changed_hash(const int index, const ll from, const ll to)const {
		const ha p(hash());
		return make_pair(
			(p.first + (to - from) * pmo_[len - index - 1].first)%mod0,
			(p.second + (to - from) * pmo_[len - index - 1].second)%mod1);
	}
};
vector<ha> RollingHash::pmo_;

	
int main() {
	ios::sync_with_stdio(false);
	int N;cin>>N;
	string st;cin>>st;
	RollingHash rh;
	rh.init(st);
	RollingHash rev_rh;
	{
		reverse(st.begin(),st.end());
		rev_rh.init(st);
		reverse(st.begin(),st.end());
	}
	int answer=0;
	for(int sz=2;sz<=N;++sz){
		bool ok=true;
		if(sz==1){
			if(st==string(N,st[0])){

			}else{
				ok=false;
			}
		}else{
			int l=0;
			bool flag=true;
			while(l<N){
				int asz=min(sz-1,N-l);
				auto a_h=rh.hash(l,l+asz-1);
				ha b_h;
				if(flag){
					b_h=rh.hash(0,asz-1);
				}else{
					b_h=rev_rh.hash(N-sz,N-sz+asz-1);
				}
				
				if(a_h!=b_h)ok=false;
				l+=sz-1;
				flag=!flag;
			}
		}
		if(ok){
			answer=sz;
			break;
		}
	}
	cout<<answer<<endl;
	return 0;	
}

### Prompt

In CPP, your task is to solve 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"
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<stack>
#include<complex>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;
	
#define WHATS(var)cout<<__LINE__<<' '<<#var<<"="<<var<<endl;
	
template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){
	os << "( " << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<T> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const set<T> &v){
	int i=0;
	for(auto it:v){
		if(i > 0){os << ' ';}
		os << it;
		i++;
	} 
	return os;
}

using ll = long long int;
using ha = pair<ll, ll>;
struct RollingHash {
	static const ll mul0 = 10009, mul1 = 10007;
	static const ll add0 = 1000010007, add1 = 1003333331;
	static const ll mod0 = 1000000007, mod1 = 1000000009;

	size_t len=0;
	//vector<ll> hash_, hash2_;
	vector<ha>hash_;
	//static vector<ll> pmo_, pmo2_;
	static vector<ha>pmo_;
	void init(const vector<ll>& s) {
		hash_.resize(len+s.size()+ 1);
		hash_[0] = make_pair(0, 0);

		if (pmo_.empty()) {
			pmo_.push_back(make_pair(1, 1));
		}
		while (pmo_.size() <= len+s.size()) {
			pmo_.push_back(make_pair(pmo_.back().first*mul0%mod0, pmo_.back().second*mul1%mod1));
		}
		for (unsigned int i = 0; i < s.size(); ++i) {
			int id=i+len;
			hash_[id + 1] = make_pair((hash_[id].first * mul0 + s[i])%mod0, (hash_[id].second*mul1 + s[i])%mod1);
		}
		len += s.size();

		return;
	}
	void init(const string& s) {
		vector<ll>v;
		for (char c : s) {
			v.push_back(c);
		}
		init(v);
	}
	ha hash(const int l, const int r)const { // s[l..r]
		auto p=make_pair(hash_[r + 1].first - hash_[l].first * pmo_[r + 1 - l].first,
			hash_[r + 1].second - hash_[l].second * pmo_[r + 1 - l].second);
		
		p.first%=mod0;
		p.second%=mod1;
		if(p.first<0)p.first+=mod0;
		if(p.second<0)p.second+=mod1;

		return p;
	}
	ha  hash()const { // s[all]
		return hash(0, len - 1);
	}

	static ha concat(const ha L, const ha R, const int RLength) { // hash(L+R) 
		return make_pair((R.first + L.first*pmo_[RLength].first)%mod0, (R.second + L.second*pmo_[RLength].second)%mod1);
	}

	ha get_changed_hash(const int index, const ll from, const ll to)const {
		const ha p(hash());
		return make_pair(
			(p.first + (to - from) * pmo_[len - index - 1].first)%mod0,
			(p.second + (to - from) * pmo_[len - index - 1].second)%mod1);
	}
};
vector<ha> RollingHash::pmo_;

	
int main() {
	ios::sync_with_stdio(false);
	int N;cin>>N;
	string st;cin>>st;
	RollingHash rh;
	rh.init(st);
	RollingHash rev_rh;
	{
		reverse(st.begin(),st.end());
		rev_rh.init(st);
		reverse(st.begin(),st.end());
	}
	int answer=0;
	for(int sz=2;sz<=N;++sz){
		bool ok=true;
		if(sz==1){
			if(st==string(N,st[0])){

			}else{
				ok=false;
			}
		}else{
			int l=0;
			bool flag=true;
			while(l<N){
				int asz=min(sz-1,N-l);
				auto a_h=rh.hash(l,l+asz-1);
				ha b_h;
				if(flag){
					b_h=rh.hash(0,asz-1);
				}else{
					b_h=rev_rh.hash(N-sz,N-sz+asz-1);
				}
				
				if(a_h!=b_h)ok=false;
				l+=sz-1;
				flag=!flag;
			}
		}
		if(ok){
			answer=sz;
			break;
		}
	}
	cout<<answer<<endl;
	return 0;	
}

```