Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

* l_1 + len \leq l_2

* S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)




If there is no such integer len, print 0.

Constraints

* 2 \leq N \leq 5 \times 10^3
* |S| = N
* S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


N
S


Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Examples

Input

5
ababa


Output

2


Input

2
xy


Output

0


Input

13
strangeorange


Output

5
import java.util.ArrayList;
import java.util.Scanner;
class Main{


	static final int MOD = 1000000007;


	static int ans = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();

		 String ss = sc.next();
		 int[][] dp = new int[n][n];
		 dp[0][0] = 1;
		 int ans = 0;
		 for(int i = 0;i < n;i++){
			 for(int j = i+1;j < n;j++){
				 if(ss.charAt(i) == ss.charAt(j)){
					 if(i == 0){
						 dp[i][j] = 1;
					 }else{
						 if(j-i > dp[i-1][j-1]){
							 dp[i][j] = dp[i-1][j-1] + 1;
						 }else{
							 dp[i][j] = dp[i-1][j-1];
						 }
					 }
				 }else{
					 dp[i][j] = 0;
				 }
				 ans = Math.max(ans, dp[i][j]);
			 }
		 }
//		 
//		 for(int i= 0;i < n;i++){
//			 for(int j = 0;j < n;j++){
//				 System.out.print(dp[i][j]);
//
//			 }
//			 System.out.println();
//		 }
		 
		 System.out.println(ans);

		


		


		




	}
	
	
	static int dfs(int x,int y,int b){
//		
		if(b < 0){
			return 0;
		}
		if(b % 3 != 0){
//			System.out.println(0);
			return 0;
		}
		if(y == 2*x){
//			System.out.println(1);
//			System.out.println(11);

			return 1;
		}else if(y == 0.5*x){
//			System.out.println(1);

			return 1;
		}else if((double)y/x > 2 ||(double)y/x < 0.5){
//			System.out.println(0);
			return 0;
		}else{
			
			int uehazix = b/3;
			int uehaziy = -uehazix + b;
			int sitahazix = 2*b/3;
			int sitahaziy = -uehazix + b;
			if(Math.abs(uehazix - x)== Math.abs(sitahazix - x)){
				return 2*dfs(x-2, y-1, b-3);
			}
			int dif = Math.min(Math.abs(uehazix - x), Math.abs(sitahazix - x));
			
			if(dif == 1){
				return b/3;
			}
			return (dfs(x-2, y-1, b-3) + dfs(x-1, y-2, b-3))%MOD;
		}
		

		
	}

	static void sieve(ArrayList<Long> list){
		int n = 50000000;
		boolean[] is_prime = new boolean[n+1];
		int[] prime = new int[n];
		for(int i= 0;i <=n;i++){
			is_prime[i] = true;
		}
		list.add((long) 1);
		for(int i = 2;i <= n;i++){
			if(is_prime[i]){
				list.add((long)i);
				for(int j = 2*i;j <= n;j+=i){
					is_prime[j] = false;
				}
			}
		}



	}




	static int upperbond(int k,int min,int[] data){		//kより小さい最大の値をdataの中から探し、返す二分探索
		int max = data.length;
		//		if(min == data.length-1){
		//			if(data[min] > k){
		//				return min;
		//			}
		//		}

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] >= k){
				max = mid;
			}else{
				min = mid;
			}
		}

		return max;
	}

	static int lowerbond(int k,int min,int[] data){		//kより大きい最小の値をdataの中から探し、返す二分探索
		int max = data.length;

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] >= k){
				max = mid;
			}else{
				min = mid;
			}
		}
		return min;
	}



	static int gcd(int a,int b){				//最大公約数を返す
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}
	static long gcd(long a,long b){
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}



	static long lcm (long a, long b) {
		long g = gcd(a,b);
		return a/g*b;
	}




}

class Town{
	int index;
	int x ;
	int y;
	public Town(int index,int x,int y) {
		this.index = index;
		this.x = x;
		this.y = y;
		// TODO 自動生成されたコンストラクター・スタブ
	}
	
	
}


class Edge extends ArrayList<P>{

}

class P{
	int to;
	long cost;
	P(int to,long cost){
		this.to = to;
		this.cost = cost;
	}
}


class Pair implements Comparable{
	int from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return   from- otherpair.from;
	}








}




