5
ababa
 8
aaabcabc
 7
abcdabc
 29
abbabbaabbbbaababbababbaabbaa
 5
baaaa
 54
dgafkhlgdhjflkdafgjldjhgkjllfallhsggaaahkaggkhgjgflsdg
 7
abcdbcd
 20
ccbbcbaabcccbabcbcaa
 11
ababcabcabc
 9
azxcvzxcv
 10
wvwlwvwwvw
 11
ababababccc
 7
dabcabc
 6
abcabd
 12
ababababvvvv
 11
jjlkalfhdhh
 6
abbbba
 8
ababcdef
 10
ababcababc
 7
ababbcc
 6
ablfab
 45
bbbbbbbabababbbaabbbbbbbbbbbbabbbabbaabbbabab
 100
mhnzadklojbuumkrxjayikjhwuxihgkinllackcavhjpxlydxcmhnzadklojbuumkrxjayikjhwuxihgkinllackcavhjpxlydxc
 5
aaaaa
 99
lhgjlskfgldjgadhdjjgskgakslflalhjfgfaaalkfdfgdkdffdjkjddfgdhalklhsgslskfdhsfjlhgajlgdfllhlsdhlhadaa
 10
adadadadad
 46
kgadjahfdhjajagdkffsdfjjlsksklgkshfjkjdajkddlj
 7
aabcdaa
 1
s
 4
ttob
 16
abcdabcdabcdabcd
 1
a
 37
lglfddsjhhaagkakadffkllkaagdaagdfdahg
 7
aabaaaa
 12
abaabaabaaba
 27
aaaaaaaaaaaaaaaaaaaaaaaaaaa
 17
abcdefggggglelsoe
 32
bbbbaaabbaabbaabbabaaabaabaabaab
 9
abbbbabbb
 10
asdasdasda
 10
bbbbbbbbbc
 11
abcabcabcab
 20
aabaabaabaabaabaabaa
 8
abcabcde
 6
abcaca
 7
aabcabc
 100
yeywsnxcwslfyiqbbeoaawtmioksfdndptxxcwzfmrpcixjbzvicijofjrbcvzaedglifuoczgjlqylddnsvsjfmfsccxbdveqgu
 16
bbbbbbaaaaaaaaaa
 77
babbaababaabbaaaabbaababbbabaaaabbabaaaaaaaabbbaaabbabbbabaababbabaabbbbaaabb
 8
aaaaaaaa
 6
ababab
 3
lsl
 12
wwvwwvwwvwwv
 10
ababababab
 8
ffffffff
 10
abcdeeeeee
 8
abbbbbba
 16
uuuuuuuuuuuuuuuu
 9
baaaabaaa
 7
zabcabc
 6
aaaaaa
 8
abcdeabc
 12
ababababbbbb
 14
abcdefgabcdepq
 6
ajkoaj
 3
aaa
 81
aaaaaababaabaaaabaaaaaaaabbabbbbbabaabaabbaaaababaabaababbbabbaababababbbbbabbaaa
 8
abcdefef
 8
abbababa
 9
abcdeabcd
 14
abcabcabcabcjj
 8
acacacac
 86
ssjskldajkkskhljfsfkjhskaffgjjkskgddfslgjadjjgdjsjfsdgdgfdaldffjkakhhdaggalglakhjghssg
 11
abcdeabcdfg
 38
asdsssdssjajghslfhjdfdhhdggdsdfsfajfas
 10
bbbbbbbaaa
 8
baaaaaaa
 5
abcbc
 8
ababcabc
 66
ldldgjllllsdjgllkfljsgfgjkflakgfsklhdhhallggagdkgdgjggfshagjgkdfld
 92
bbbbbabbbaaaabaaababbbaabbaabaaabbaabababaabbaabaabbbaabbaaabaabbbbaabbbabaaabbbabaaaaabaaaa
 10
abcabcabca
 5
aabaa
 12
abcabcabcabc
 8
aaaabcde
 8
abbbbbbb
 10
abcabcdddd
 20
abcdabcdeeeeeeeeabcd
 5
abbbb
 16
aaaaaabbaaaaaabb
 10
aaaacaaaac
 10
aaaaaaaaaa
 7
abababa
 8
aaaaaass
 7
abacbac
 36
bbabbaabbbabbbbbabaaabbabbbabaabbbab
 8
aabcabca
 10
abccaaaaba
 8
asafaass
 14
aaabcabcabcabc
 79
lsfgfhhhkhklfdffssgffaghjjfkjsssjakglkajdhfkasfdhjhlkhsgsjfgsjghglkdkalaajsfdka
 7
mabcabc
 17
ababababzabababab
 8
abababaa
 10
abcdabcefg
 17
abcdefgggggabcdef
 13
eabcdefabcdef
 8
abababab
 28
aaaaaaaaaaaaaaibfprdokxvipsq
 13
aabbbkaakbbbb
 4
abab
 9
zabcdabcd
 70
babababbabababbbabaababbababaabaabbaaabbbbaababaabaabbbbbbaaabaabbbabb
 9
abcabcabc
 2
aa
 100
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
 4
aaaa
 36
babbbbababaaabbabbbaabaabbbbbbbbbbba
 9
asdfgasdf
 13
aabaabaabaabx
 95
bbaaaabaababbbabaaaabababaaaaaabbababbaabbaaabbbaaaabaaaaaaababababbabbbaaaabaabaababbbbbababaa
 5
xabab
 20
hhhhhhhhhhhhhhhhhhhh
 41
abbababbbbbabbbabaaaababaaabaabaaabbbbbbb
 8
pppppppp
 5
abcab
 10
avavavavbc
 12
aaaaaaaaaaaa
 63
jhkjhadlhhsfkadalssaaggdagggfahsakkdllkhldfdskkjssghklkkgsfhsks
 9
aaaaaaaaa
 6
abcbcd
 16
aaaaaaaaaaaaaaaa
 9
asdfpasdf
 12
aabaabaabaab
 74
ghhhfaddfslafhhshjflkjdgksfashhllkggllllsljlfjsjhfggkgjfalgajaldgjfghlhdsh
 39
jflfashaglkahldafjasagasjghjkkjgkgffgkk
 10
adcbeadcfg
 5
cabab
 6
ababbb
 99
trolnjmzxxrfxuexcqpjvefndwuxwsukxwmjhhkqmlzuhrplrtrolnjmzxxrfxuexcqpjvefndwuxwsukxwmjhhkqmlzuhrplrm
 7
abcaabc
 6
aabbbb
 87
fhjgjjagajllljffggjjhgfffhfkkaskksaalhksfllgdjsldagshhlhhgslhjaaffkahlskdagsfasfkgdfjka
 8
baaaaaab
 5
aavaa
 5
aabab

4
 8
 7
 27
 5
 54
 7
 20
 10
 9
 10
 8
 7
 6
 9
 11
 6
 7
 6
 6
 6
 43
 51
 4
 99
 7
 46
 7
 1
 4
 9
 1
 37
 7
 7
 15
 17
 31
 9
 8
 7
 9
 12
 6
 6
 7
 100
 14
 77
 5
 5
 3
 7
 7
 5
 10
 8
 9
 9
 7
 4
 8
 9
 14
 6
 3
 79
 8
 8
 9
 9
 5
 86
 11
 38
 8
 8
 5
 7
 65
 91
 8
 5
 7
 7
 8
 8
 17
 5
 9
 6
 6
 6
 6
 7
 34
 8
 10
 8
 14
 79
 7
 14
 7
 10
 17
 13
 5
 22
 13
 3
 9
 64
 7
 2
 51
 3
 36
 9
 8
 95
 5
 11
 41
 5
 5
 7
 7
 63
 6
 6
 9
 9
 7
 74
 39
 10
 5
 5
 51
 7
 6
 87
 8
 5
 5

 import java.io.*;
    import java.util.*;
  
 
  
        public class Codeforces {
    	
    		   public static long log2(long x)
    			{
    				long p=1;
    				long ans=0;
    				while(x>=p)
    				{
    					p*=2;
    					ans++;
    				}
    				return ans-1;
    			}
    		   
    		   
    		   public static void extendedgcd(int a, int b)
    		   {
    			   x=0;
    			   y=0;
    			   gc=0;
    			   xgcd(a,b);
    			   pw.println(a+"*"+x+" + "+b+"*"+y+" = "+gc);
    			   
    		   }
    		   
    		   
    		   public static long modex(long a, long b, long c)
    		   {
    			   if(b==0)
    				   return 1;
    			   else if(b==1)
    				   return a%c;
    			   else if(b%2==0)
    			   {
    				   	return modex((a*a)%c,b/2,c);
    			   }
    			   else
    			   {
    				   return (a*modex((a*a)%c,b/2,c))%c;
    				   
    			   }
    			   
    			   
    		   }
    		   
    		   
    		   public static void xgcd(int a, int b)
    		   {
    			   
    			   if(b==0)
    			   {
    				   x=1;
    				   y=0;
    				   gc=a;
    				   
    				   
    			   }
    			   else
    			   {
    				   xgcd(b,a%b);
    				   int temp = x;
    				   x=y;
    				   y = temp - ((a/b)*y);
    				   
    			   }
    		   }
    		   
    		   public static long gcd(long a, long b)
    		   {
    			   if(b==0)return a;
    			   else return gcd(b,a%b);
    			   
    		   }
    		   
    		   static int x,y,gc;
    		   
    		  
    		
    		   
    		   static HashSet<Character> set;
    		   
    		   
    		   
    		   public static long expmod(long a, long b, long mod)
    		   {
    			   if(b==0)return 1;
    			   if(b==1)return a;
    			   
    			   if(b%2==0)
    			   {
    				   return ((expmod(a,b/2,mod)%mod)*(expmod(a,b/2,mod)%mod))%mod;
    			   }
    			   else
    			   {
    				   return ((a%mod)*(expmod(a,b/2,mod)%mod)*(expmod(a,b/2,mod)%mod))%mod;
    			   }
    		   }
    		   
    		   static class Comp implements Comparator<Point>
    		   {

				@Override
				public int compare(Point arg0, Point arg1) {
					
					if(arg0.x>arg1.x)return 1;
					if(arg0.x<arg1.x)return -1;
					return 0;
				}
    			   
    		   }
    		   
    		   
    		   static class STComp implements Comparator<Integer>
    		   {

				@Override
				public int compare(Integer arg0, Integer arg1) {
					
					return arg0.compareTo(arg1); 
				}
    			   
    		   }
    		   
    		   static class Point
    		   {
    			   int x,y,ind;
    			   
    			    public Point(int a, int b)
    			    {
    			    	x=a;
    			    	y=b;
    			    	ind=0;
    			    }
    			   
    			    @Override
    			    public boolean equals(Object o) 
    			    {
    			 
    			        // If the object is compared with itself then return true  
    			        if (o == this) {
    			            return true;
    			        }
    			 
    			        /* Check if o is an instance of Complex or not
    			          "null instanceof [type]" also returns false */
    			        if (!(o instanceof Point)) {
    			            return false;
    			        }
    			         
    			        // typecast o to Complex so that we can compare data members 
    			        Point c = (Point) o;
    			         
    			        // Compare the data members and return accordingly 
    			        return x==c.x&&y==c.y;
    			                
    			    }
    			    
    		   }
    		   
    		 
    		   
    		  
    		   
    		   public static boolean issub(String s1, String s2)
    		   {
    			   if(s1.length()>s2.length())
    			   return false;
    			   
    			   int l1 = s1.length();
    			   int l2 = s2.length();
    			   
    			   
    			   for(int i=0;i<=l2-l1;i++)
    			   {
    				   String sub = s2.substring(i, i+l1);
    				   if(s1.equals(sub))return true;
    			   }
    			   
    			   return false;
    		   }
    		   
    		   
    		   
    		   public static String enc(String s, int n)
    		   {
    			   String s1 = s.substring(0,n);
    			   String s2 = s.substring(n, s.length());
    			   
    			  String re="";
    			  for(int i=s1.length()-1;i>=0;i--)re+=s1.charAt(i);
    			  
    			  return re+s2;
    			   
    			   
    			   
    		   }
    		 
    		   
    		   
    		   static int vis[];
    		   
    		   public static void dfs(int x)
    		   {
    			   vis[x]=1;
    			   
    			   ArrayList<Integer> li = adj[x];
    			   
    			   for(int ch:li)
    			   {
    				   
    				   if(vis[ch]==0)dfs(ch);
    				   
    			   }
    			   
    		   }
    		   /*
    		   public static void dfsm(int x, HashSet<Integer> set)
    		   {
    			   vis2[x]=1;
    			   
    			   ArrayList<Integer> li = adj[x];
    			   
    			   for(int ch:li)
    			   {
    				   //if(!set.contains(ch))continue;
    				   if(vis2[ch]==0)dfsm(ch,set);
    				   
    			   }
    			   
    		   }
    		   */
    		   
    		  
    		
    		   public static void countPaths(int s, int d, ArrayList<Integer> pa)
    		   {
    			   
    			   vis2[s]=1;
    			   if(s==d)
    			   {
    				   pa.add(s);
    				 //  paths[ct] = new ArrayList<Integer>(pa);
    				   ct++;
    			   }
    			   else
    			   {
    				   ArrayList<Integer> li = adj[s];
    				   pa.add(s);
    				   
    				   for(int ad: li)
    				   {
    					   if(vis2[ad]==0)countPaths(ad,d,pa);
    				   }
    				   
    				   
    			   }
    			   
    			   if(pa.size()>1)pa.remove(pa.size()-1);
    			   vis2[s]=0;
    			   return ;
    		   }
    		  
    		   
    		   
    		   public static boolean dif(String s1, String s2)
    		   {
    			   int ct=0;
    			   if(s1.length()!=s2.length())return false;
    			   for(int i=0;i<s1.length();i++)
    			   {
    				   if(s1.charAt(i)!=s2.charAt(i))ct++;
    				   
    			   }
    			   
    			   if(ct==1)return true;
    			   else return false;
    			   
    			   
    		   }
    		   
    		   
    		   
    		   
    		   static void add(int arr[], int N, int lo,
                       int hi, int val)
    		   {
							    arr[lo] += val;
							    if (hi != N - 1)
							       arr[hi + 1] -= val;
    		   }
 
// Utility method to get actual array from 
// operation array
static void updateArray(int arr[], int N)
{
    // convert array into prefix sum array
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}
  
// method to print final updated array
static void printArr(int arr[], int N)
{
    updateArray(arr, N);
    for (int i = 0; i < N; i++)
        System.out.print(""+arr[i]+" ");
    System.out.print("\n");
}
  
    		   
  
    		  static int cyc;
    		   
    		   
    		  
    		  public static void dfsmod(int v, HashSet<Integer> set)
    		  {
    			  vis2[v]=1;
    			  
    			  ArrayList<Integer> li = adj[v];
    			  
    			  set.add(v);
    			  
    			  for(int ch: li)
    			  {
    				  if(set.contains(ch))
    				  {
    					  cyc=1;
    					  pw.println("** "+ch+" "+v);
    				  }
    				  if(vis2[ch]==0)dfsmod(ch,set);
    				  
    			  }
    			  
    			  set.remove(v);
    			  
    			  
    		  }
    		  
    		  
    		  	public static boolean isps(int x)
    		  	{
    		  		int sq = (int)Math.sqrt(x);
    		  		
    		  		return sq>0&&sq*sq==x;
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  	}
    		  
    		  	 public static void combinations(String suffix,String prefix)
    		  	 {
    		         if(prefix.length()<0)return;
    		         pw.println(suffix);
    		        	 
    		        	 
    		         for(int i=0;i<prefix.length();i++)
    		          combinations(suffix+prefix.charAt(i),prefix.substring(i+1,prefix.length()));
    		         
    		     }
    		  	
    		  	
    		  	 
    		
    		  	 
    		  	 
    		  	 public static void topo(int x)
    		  	 {
    		  		 vis2[x]=1;
    		  		// pw.println("vis "+x);
    		  		 ArrayList<Integer> li = adj[x];
    		  		// pw.println(x+" has siz "+li.size());
    		  		// Integer i = x;
    		  		 for(int ch: li)
    		  		 {
    		  			
    		  			 if(vis2[ch]==0)
    		  				 {topo(ch);
    		  				//pw.println(x+" "+ch);
    		  				 }
    		  		 }
    		  		 
    		  		 st.push(x);
    		  		 //pw.println(i+" pushed");
    		  	 }
    		  	 
    		  	 
    	  		   

    		 	static  ArrayList<Integer>[] adj;
    		 	static int[] vis2;
    		 	static int ct;

    		     public static void ch(Stack<Integer> s)
    		     {
    		    	 s.push(4);
    		    	 return;
    		     }
    		     
    		     static Stack<Integer> st;
    		     
    		     
    		     static class PQnode implements Comparable<PQnode>
    		     {
    		    	 int value;
    		    	 int distance;
    		    	 
    		    	 public PQnode(int x, int y)
    		    	 {
    		    		 value=x;
    		    		 distance=y;
    		    	 }

					@Override
					public int compareTo(PQnode o) {
					return Integer.compare(this.distance, o.distance);
						
					
					
					}
					
					
					  @Override
		    		    public  boolean equals(Object o)
		    		    {
		    		    	if(o==this)return true;
		    		    	
		    		    	if(!(o instanceof PQnode))
		    		    	{
		    		    		return false;
		    		    	}
		    		    	
		    		    	PQnode node = (PQnode) o;
		    		    	
		    		    	return value==node.value&&distance==node.distance;
		    		    	
		    		    }
    		     }
    		  
    		  
    		     static class Compq implements Comparator<PQnode>
    		     {

					
					public int compare(PQnode arg0, PQnode arg1) 
					{
						
						if(arg0.distance>arg1.distance)return 1;
						if(arg0.distance<arg1.distance)return -1;
						return 0;
					}
    		    	 
    		    	 
    		    	 
    		     }
    		     
    		     public static void printpa(int pa[],int x)
    		     {
    		    	 if(pa[x]==-1)
    		    		 
    		    		 pw.println(x);
    		    	 else
    		    	 {
    		    		 printpa(pa, pa[x]);
    		    		 pw.println(x);
    		    	 }
    		     }
    		     
    		     
    		     static class Node
    		     {
    		    	 int data;
    		    	 Node next;
    		    	 
    		    	 public Node(int x)
    		    	 {
    		    		 data =x;
    		    		 next=null;
    		    	 }
    		     }
    		     
    		     static Node he;
    		     static Node rev(Node n)
    		     {
    		    	 if(n.next==null)
    		    	 {
    		    		he=n;
    		    		return n;
    		    		 
    		    	 }
    		    	 else
    		    	 {
    		    		 Node rt = rev(n.next);
    		    		 rt.next=n;
    		    		 return n;
    		    	 }
    		    	 
    		     }
    		     
    		     
    		     
    		     
    		     public static int trap(final int[] A) {
    		    	    
    		         int n = A.length;
    		         int arr[] = new int[A.length];
    		         for(int i=0;i<A.length;i++)arr[i]=A[i];
    		         int nge[] = new int[A.length];
    		         
    		         Stack<Point> st = new Stack<Point>();
    		         //int ip=0;
    		         
    		        
    		         
    		         st.push(new Point(arr[0],0));
    		         
    		         for(int i=1;i<n;i++)
    		         {
    		             Point p = new Point(arr[i],i);
    		             
    		             while(!st.isEmpty()&&p.x>=st.peek().x)
    		             {
    		                 Point pop = st.pop();
    		                 nge[pop.y]=p.y;
    		             }
    		             st.push(p);
    		             
    		         }
    		         
    		         while(!st.isEmpty())
    		         {
    		             Point p = st.pop();
    		             nge[p.y]=-1;
    		         }
    		         
    		         int ans=0;
    		        for(int i=0;i<n;i++)System.out.print(nge[i]+" ");
    		        pw.println(); 
    		        for(int i=0;i<n;)
    		         {
    		             if(arr[i]!=0)
    		             {
    		                 int ng = nge[i];
    		                 if(ng==-1)
    		                 {
    		                   int j=i+1;
    		                   while(j<n&&arr[j]==0)j++;
    		                   
    		                   if(j!=n)
    		                   {int ad = (j-i-1)*arr[j];
    		                       ans+=ad;
    		                     System.out.println("1* "+i+" "+j+" "+ad);
    		                     i=j;
    		                     
    		                   }
    		                  
    		                   
    		                 }
    		                 else
    		                 {
    		                    int sub=0;
    		                    int j = i+1;
    		                    while(j<n&j<ng)
    		                    {
    		                        sub+=arr[j];
    		                        j++;
    		                    }
    		                    
    		                    int ad = (arr[i]*(ng-i-1))-sub;
    		                    System.out.println("2* "+i+" "+j+" "+ng+" "+ad);
    		                    ans += ad;
    		                    
    		                    i=ng;
    		                     
    		                 }
    		             }
    		             else
    		             {
    		            	 i++;
    		             }
    		         }
    		         
    		         
    		         return ans;
    		         
    		     }
    		     
    		     
    		     
    		     public static int round(int st, int end, int a, int b)
    		     {
    		    	 int mid = (st+end)/2;
    		    	 
    		    	 if(a<=mid&&b>=mid+1)return 0;
    		    	 else
    		    	 {
    		    		 if(a<=mid&&b<=mid)
    		    		 {
    		    			 return 1+round(st,mid,a,b);
    		    			 
    		    		 }
    		    		 else
    		    		 {
    		    			 return 1+round(mid+1,end,a,b);
    		    			 
    		    		 }
    		    		 
    		    	 }
    		    	 
    		    	 
    		    	 
    		     }
    		     
    		     
    		     
    		     public static void cha(Point p)
    		     {
    		    	 p.x=10;
    		    	 p.y=5;
    		     }
    		     
    		     
    		     
    		     public static void main(String[] args) throws IOException 
    	   {

    		    	 int n = sc.nextInt();
    		    	 
    		    	 String st=sc.nextLine();
    		    	 
    		    	 int up=-1;
    		    	 int k,wk=-1;
    		    	 for( k=1;(2*k+1)<n;k++)
    		    	 {
    		    		 String s1 = st.substring(0, k+1);
    		    		 String s2 = st.substring(k+1, 2*(k+1));
    		    		// pw.println(s1+" "+s2);
    		    		 if(s1.equals(s2))
    		    		 {
    		    			//pw.println(s1);
    		    			 up=2*(k+1)-1;
    		    			 wk=k;
    		    		 }
    		    		 
    		    		 
    		    		 
    		    	 }
    		    	// pw.println(wk);
    		    	 
    		    	 
    		    	 int nas=0;
    		    	 nas+=(wk+1);
    		    	 if(wk>0)nas++;
    		    	 
    		    	 nas+=(n-1-up);
    		    	 pw.println(nas);
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 /*
    		    	 HashMap<Integer,Integer> ts = new HashMap<Integer,Integer>();
    		    	
    		    	ts.put(8,1);
    		    	ts.put(3,1);
    		    	ts.put(5,1);
    		    	
    		    	int arr[] = new int[ts.size()];
    		    	
    		    	Object[] ar2 = ts.keySet().toArray();
    		    	
    		    	int ar3[] = new int[ar2.length];
    		    	
    		    	
    		    		
    		    	for(int i=0;i<ar2.length;i++)
    		    	{
    		    		ar3[i] = (int)ar2[i];
    		    		pw.println(ar3[i]);
    		    	}
    		    	
    		    	int d = 5;
    		    	
    		    	int m = 1<<2;
    		    	
    		    	pw.println(m&d);
    		    	*/
    		    	//int[] arr = ts.toArray(new int[ts.size()]);
    		    	
    		    	
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	/*int dist = (be-ae)/2;
    		    	
    		    	int ct=0;
    		    	while(dist!=0)
    		    	{
    		    		dist/=2;
    		    		ct++;
    		    	}
    		    	 
    		    	int rn = ct+1;
    		    	
    		    
    		    	
    		    	pw.println(l2);
    		    	
    		    	if(rn==l2)
    		    	{
    		    		pw.println("Final!");
    		    	}
    		    	else
    		    	{
    		    		
    		    		pw.println(rn);
    		    	}
    		    	*/
    		    	
    		    	
    		    	 /*int a[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    		    	 for(int i=0;i<a.length;i++)pw.print(a[i]+" ");
    		    	 pw.println();
    		    	 trap(a);*/
    		    	 
    		    	 /*
    		    	 int n = sc.nextInt();
    		    	 int a  = sc.nextInt();
    		    	 int b = sc.nextInt();
    		    	 long sum=0;
    		    	 
    		    	 int arr[] = new int[n];
    		    	 
    		    	 for(int i=0;i<n;i++)
    		    	 {	 arr[i]=sc.nextInt();
    		    	 	sum+=arr[i];
    		    	 }
    		    	 
    		    	 
    		    	 int as = (arr[0]*a)/b;
    		    	 
    		    	 int bl[] = new int[n-1];
    		    	 
    		    	 for(int i=1;i<n;i++)
    		    	 {
    		    		 bl[i-1]=arr[i];
    		    	 }
    		    	 
    		    	 Arrays.sort(bl);
    		    	 
    		    	 if(sum<=as)
    		    	 {
    		    		 pw.println(0);
    		    		 pw.close();
    		    		 return;
    		    	 }
    		    	 
    		    	 int ans=0;
    		    	 for(int i=n-2	;i>=0;i--)
    		    	 {
    		    		 sum = sum-bl[i];
    		    		 ans++;
    		    		 if(sum<=as)break;
    		    		 
    		    	 }
    		    		 pw.println(ans);
    		    	 
    		    	 */
    		    			 
    		    			 
    		    	 
    		    	 
    		    	 
    		    	 

    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    			 
    		    	 
    		    	 
    		    	 
    		    	
    		    	//pw.println(ans);
    		    	 
    		    	 /*int n  =sc.nextInt();
    		  		int k = sc.nextInt();
    		  		
    		  		int arr[] = new int[n];
    		  		
    		  		for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    		  		
    		  		int pref[] =  new int[n];
    		  		
    		  		for(int i=0;i<n;i++)
    		  		{
    		  			if(i==0)
    		  			{
    		  				pref[i]=arr[i];
    		  			}
    		  			else
    		  			{
    		  				pref[i]=pref[i-1]+arr[i];
    		  			}
    		  		}
    		  				
    		  		double ans = Float.MIN_VALUE;
    		  		
    		  		
    		  		
    		  		for(int i=k;i<=n;i++)
    		  		{
    		  			
    		  			int p1 = 0;
    		  			int p2= i-1;
    		  			
    		  			while(p2<=n)
    		  			{
    		  				//pw.println("calc "+p1+" "+p2);
    		  				double rsum = (p1==0)?pref[p2]:pref[p2]-pref[p1-1];
    		  				double avg = rsum/i;
    		  				//pw.println(i);
    		  				ans = Math.max(ans, avg);
    		  				p1++;
    		  				p2++;
    		  				//pw.println("********");
    		  				if(p2==n)break;
    		  			}
    		  			
    		  		}
    		    	 
    		  		pw.println(ans);
    		    	 */
    		    	 
    		    	 /*
    		    	 */
    		    	
    		    	
    		    	
    		    	/* 
    		    	Node n1 = new Node(1);
    		    	Node n2 = new Node(2);
    		    	Node n3 = new Node(3);
    		    	n1.next=n2;
    		    	n2.next=n3;
    		    	n3.next=null;
    		    	
    		    	rev(n1);
    		    	
    		    	while(he!=null)
    		    	{
    		    		pw.println(he.data);
    		    		he=he.next;
    		    	}
    		    	 */
    		    	 /* 
    		    	int n = sc.nextInt();
    		  		 
    		  		int x = sc.nextInt();
    		  		int y = sc.nextInt();
    		  		
    		  		String st = sc.nextLine();
    		  		int ind[] = new int[n];
    		  		int indct=0;
    		  		for(int i=0;i<st.length();i++)
    		  		{
    		  			if(st.charAt(i)=='1')
    		  			{
    		  				ind[indct++]=i;
    		  			}
    		  			
    		  		}
    		  		
    		  		
    		  		int r=0;
    		  		if(indct==0||indct==1)
    		  		{
    		  			if(indct==0)
    		  			{
    		  				pw.println(y);
    		  				pw.close();
    		  				return;
    		  			}
    		  			else
    		  			{
    		  				r=1;
    		  			}
    		  		}
    		  		
    		  		
    		  		else
    		  		{
    		  		
    		  		for(int i=0;i<indct-1;i++)
    		  		{
    		  			if(ind[i+1]-ind[i]>1)r++;
    		  		}
    		  		
    		  		if(r==0)
    		  		{
    		  			if(r==0)
    		  			{
    		  				pw.println(0);
    		  				pw.close();
    		  				return;
    		  			}
    		  			
    		  		}
    		  		
    		  		r++;
    		  		
    		  		}
    		  		
    		  		
    		  		//pw.println("r "+r);
    		  		
    		  		
    		  		long ans = Long.MAX_VALUE;
    		  		
    		  		for(int rev=0;rev<=r;rev++)
    		  		{
    		  			long left = r-rev;
    		  			long p = (left+1)*y + x*rev;
    		  			//pw.println(" p "+p);
    		  			ans = Math.min(p, ans);
    		  		}
    		  		
    		  		
    		  		pw.println(ans);
    		  		 */
    		  			
    		  				
    		  		 
    		  		 /*PriorityQueue<PQnode> pq = new PriorityQueue<PQnode>();
    		  		
    		  		 pw.println(pq.size());
    		  		 
    		  		 pq.add(new PQnode(1,2));
    		  		 pq.add(new PQnode(3,4));
    		  		 
    		  		 pw.println(pq.size());
    		  		pq.remove(new PQnode(1,2));
    		  		 pw.println(pq.size());
    		  		 
    		  		 
    		  		 
    		  		 int parent[] = new int[4];
    		  		 Arrays.fill(parent, -1);
    		  		 ArrayList<Point> adj[] = new ArrayList[4];
    		  		 
    		  		 for(int i=0;i<4;i++)adj[i] = new ArrayList<Point>();
    		  		 
    		  		 adj[0].add(new Point(1,10));
    		  		 adj[0].add(new Point(2,20));
    		  		 
    		  		 adj[1].add(new Point(0,10));
    		  		adj[1].add(new Point(2,5));
    		  		adj[1].add(new Point(3,16));
    		  		
    		  		adj[2].add(new Point(0,20));
    		  		adj[2].add(new Point(1,5));
    		  		adj[2].add(new Point(3,20));
    		  		
    		  		adj[3].add(new Point(1,16));
    		  		adj[3].add(new Point(2,20));
    		  		 
    		  		 
    		  		 
    		  		 PriorityQueue<PQnode> pq = new PriorityQueue<PQnode>(new Compq());
    		  		 HashSet<Integer> pres = new HashSet<Integer>();
    		  		 
    		  		 int[] dist = new int[4];
    		  		 
    		  		 for(int i=0;i<4;i++)
    		  		 {
    		  			 if(i==0)
    		  			 {
    		  				pq.add(new PQnode(i,0)); 
    		  				dist[i]=0;
    		  			 }
    		  			 else
    		  			 {
    		  				 pq.add(new PQnode(i,Integer.MAX_VALUE));
    		  				 dist[i]=Integer.MAX_VALUE;
    		  			 }
    		  			 pres.add(i);
    		  			 
    		  		 }
    		  		 
    		  		 
    		  		 while(!pq.isEmpty())
    		  		 {
    		  			 PQnode pop = pq.poll();
    		  			 pres.remove(pop.value);
    		  			// pw.println(pop.value+" "+pop.distance);
    		  			 dist[pop.value]=pop.distance;
    		  			 for(Point p: adj[pop.value])
    		  			 {
    		  				 if(pres.contains(p.x))
    		  				 {
    		  					 if(p.y+dist[pop.value]<dist[p.x])
    		  					 {
    		  						 pw.println("ha");
    		  						
    		  						 pq.remove(new PQnode(p.x,dist[p.x]));
    		  						 dist[p.x]=p.y+dist[pop.value];
    		  						 pq.add(new PQnode(p.x,p.y+dist[pop.value]));
    		  						 parent[p.x]=pop.value;
    		  					 }
    		  				 }
    		  			 }
    		  			 
    		  		 }
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 for(int i=0;i<4;i++)pw.print(dist[i]+" ");
    		  		pw.println();
    		  		 printpa(parent, 3	);
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 Dijkstra over.
    		  		 */
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 /*
    		  		st = new Stack<Integer>();
    		  		 
    			 
    			  cyc=0;
       			adj = new ArrayList[4];
       			vis2 = new int[4];
       			
       			Arrays.fill(vis2, 0);
       			for(int i=0;i<4;i++)adj[i] = new ArrayList<Integer>();
       			   
       			
       			adj[0].add(1);
       			adj[0].add(2);
       			adj[0].add(3);
       			
       			adj[1].add(3);
       			
       			//adj[2].add(0);
       			adj[2].add(1);
    			   //adj[3].add(2);
    			   
       			st = new Stack<Integer>();
    			
       			topo(0);
    			   
    			 while(!st.isEmpty())pw.println(st.pop());
    			 */
    				 
    			/*
    			int n = sc.nextInt();
    			
    			int arr[] = new int[n];
    			
    			for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    			
    			long ansg =0,ansv = Long.MAX_VALUE; 
    			
    			int arr2[] = new int[n];
    			for(int i=0;i<n;i++)arr2[i]=arr[i]-i;
    		
    			for(int i=0;i<n;i++)
    			{
    				int x = arr2[i];
    				
    				if(x<=0)
    				{
    					
    					if(i<ansv)
    					{
    						
    						ansg=i;
    						ansv=i;
    					}
    				}
    				else
    				{
    					float t = ((float)x)/n;
    					long tt = (long)Math.ceil(t);
    					
    					long ex = i;
    					long ti = tt*n+ex;
    					
    					
    					if(ti<ansv)
    					{
    						//pw.println("** "+i);
    						ansg=i;
    						ansv=ti;
    					}
    					
    				}
    				
    				
    				
    			}
    			
    			pw.println(ansg+1);
    			*/
    			   
    			   
    			   
    		
    			   
    			   
    	
    			   
    			   /*ct=0;
    			
    			paths= new ArrayList[10];
    			adj = new ArrayList[4];
    			vis2 = new int[4];
    			
    			for(int i=0;i<4;i++)adj[i] = new ArrayList<Integer>();
    			   
    			for(int i=0;i<10;i++)paths[i] = new ArrayList<Integer>();
    			
    			adj[0].add(1);
    			adj[0].add(2);
    			adj[0].add(3);
    			
    			adj[1].add(3);
    			
    			adj[2].add(0);
    			adj[2].add(1);
    			
    			countPaths(2,3, new ArrayList<Integer>());
    			pw.println(ct);
    			   
    			for(int i=0;i<ct;i++)pw.println(paths[i]);
    			  */ 
    			   
    			   
    			   
    			   /*
    			   int n = sc.nextInt();
    			int m = sc.nextInt();
    			
    			int arr[] = new int[n];
    			
    			for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    			
    			int req = n/m;
    			
    			int[] rem = new int[m];
    			
    			
    			HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    			for(int i=0;i<n;i++)
    			{
    				rem[arr[i]%m]++;
    				
    			}
    			int li=-1;
    			long ans=0;
    			for(int i=0;i<m;i++)
    			{
    				if(rem[i]>=req)
    				{
    					rem[(i+1)%m]+=rem[i]-req;
    					ans+=(rem[i]-req);
    				}
    				else
    				{
    					li=i;
    					
    				}
    			}
    			
    			for(int i=0;i<li;i++)
    			{
    				if(rem[i]>=req)
    				{
    					rem[(i+1)%m]+=rem[i]-req;
    					ans+=(rem[i]-req);
    				}
    				else
    				{
    					li=i;
    					
    				}
    			}
    			pw.println(ans);
    			*/
    			
    			
    			
    			   //pw.println(pa);
    		/*	  NGE 
       		int[] sto = {100,80,60,70,60,75,85};
       		int n = sto.length;
       		
       		int[] spa = new int[n];
       		spa[0]=1;
       		
       		Stack<Integer> st = new Stack<Integer>();
       		st.push(0);
       		
       		for(int i=1;i<n;i++)
       		{
       			
       			while(!st.isEmpty()&&sto[st.peek()]<=sto[i])st.pop();
       			
       			spa[i]=(st.isEmpty())?i+1:i-st.peek();
       			st.push(i);
       			
       		}
    			  
       		
       		for(int i=0;i<n;i++)pw.print(sto[i]+" ");
    			   pw.println();
    			   for(int i=0;i<n;i++)pw.print(spa[i]+" ");
    			  
    			   
    			   int[] nge = new int[n];
    			   
    			   st.clear();
    			   Stack<Point> st2 = new Stack<Point>();
    			   st2.push(new Point(sto[0],0));
    			   
    			   for(int i=1;i<n;i++)
    			   {
    				   while(!st2.isEmpty()&&st2.peek().x<sto[i])
    				   {
    					   Point pop = st2.pop();
    					   nge[pop.y]=sto[i];
    				   }
    				   st2.push(new Point(sto[i],i));
    				   
    			   }
    			   
    			   while(!st2.isEmpty())
    			   {
    				   nge[st2.pop().y]=-1;
    			   }
    			  
    			   pw.println();
    			   for(int i=0;i<n;i++)pw.print(sto[i]+" ");
    			   pw.println();
    			   for(int i=0;i<n;i++)pw.print(nge[i]+" ");
    			 */ 
    			   
    			   /*  int r = 2000000000;
    			  pw.println(r);
    			int n = sc.nextInt();
    			int k = sc.nextInt();
    			int l = sc.nextInt();
    			int m = n*k;
    			int arr[] = new int[m];
    			
    			for(int i=0;i<m;i++)arr[i]=sc.nextInt();
    			
    			Arrays.sort(arr);
    			
    			int limit = l+arr[0];
    			int li=-1;
    			
    			for(int i=0;i<m;i++)
    			{
    				//pw.println(arr[i]);
    				if(arr[i]>limit)
    				{
    					//pw.println(arr[i]);
    					li=i; break;
    				}
    			}
    			//pw.println(limit+" "+li);
    			if(li==-1)li=n;
    			
    			int noofsmallest = li;
    			
    			if(noofsmallest<n)
    			{
    				pw.println(0);
    			}
    			else
    			{
    				li--;
    				long ans=0;
    				for(int i=0;i<n-1;i++)
    				{
    					ans+=(long)arr[li];
    					li--;
    				}
    				ans+=arr[0];
    				pw.println(ans);
    				
    			}
    			  */ 
    	
    			 
    			  
    			pw.close();  
    			   
    	   }
    		   
    		   
    		   
    		   static  class MyScanner 
    			{
    	
    			BufferedReader br;
    			StringTokenizer st;
    			
    			public MyScanner() 
    			{
    				br = new BufferedReader(new InputStreamReader(System.in));
    			}
    	
    			String next() 
    			{
    				
    				while (st == null || !st.hasMoreElements()) 
    				{
    					try 
    					{
    						st = new StringTokenizer(br.readLine());
    					} catch (IOException e) 
    					{
    						e.printStackTrace();
    					}
    				}
    				return st.nextToken();
    			}
    	
    			int nextInt() 
    			{
    				return Integer.parseInt(next());
    			}
    	
    			long nextLong() 
    			{
    				return Long.parseLong(next());
    			}
    	
    			double nextDouble() 
    			{
    				return Double.parseDouble(next());
    			}
    	
    			String nextLine()
    			{
    				String str = "";
    				try 
    				{
    					str = br.readLine();
    				} catch (IOException e) 
    				{
    					e.printStackTrace();
    				}
    				return str;
    			}
    	
    		}
    	
    		static MyScanner sc = new  MyScanner();
    		static PrintWriter pw = new PrintWriter(System.out, true);
    		
    		static class DisjointSet
    		{
    			int[] parent;
    			int[] rank;
    			int n;
    			
    			public DisjointSet(int x)
    			{
    				n=x;
    				parent = new int[x];
    				rank = new int[x];
    				
    				for(int i=0;i<n;i++)
    				{
    					parent[i]=i;
    				}
    				
    			}
    			
    			public int find(int x)
    			{
    				
    				if(parent[x]==x)
    					return x;
    				else 
    					return find(parent[x]);
    			}
    			
    			public void union(int i, int j)
    			{
    				int iroot = find(i);
    				int jroot = find(j);
    				
    				if(iroot==jroot)
    					return;
    				
    				if(rank[iroot]<rank[jroot])
    				{
    					parent[iroot]=jroot;
    					
    				}
    				else if(rank[jroot]<rank[iroot])
    				{
    					parent[jroot]=iroot;
    				}
    				else
    				{
    					parent[iroot]=jroot;
    					rank[jroot]++;
    					
    				}
    				
    				
    				
    				
    			}
    			
    			
    			
    			
    			
    		}
    	
    		
    	}  