You are going to take the entrance examination of Kyoto University tomorrow and have decided to memorize a set of strings S that is expected to appear in the examination. Since it is really tough to memorize S as it is, you have decided to memorize a single string T that efficiently contains all the strings in S.

You have already confirmed the following conditions for S and T are satisfied.

* Every string in S is a consecutive subsequence(1) in T .
* For every pair of strings x, y (x \neq y) in S , x is not a subsequence(2) of y.



Note that (1) is ''consecutive subsequence'', while (2) is ''subsequence''.

The next day, you opened the problem booklet at the examination and found that you can get a full score only if you remember S. However, You have forgot how to reconstruct S from T . Since all you remember is that T satisfies the above conditions, first you have decided to find the maximum possible number of elements in S .

Constraints

* 1 \leq |T| \leq 10^5
* T consists of only lowercase letters.



Partial points

* 30 points will be awarded for passing the test set satisfying the condition: 1 \leq |T| \leq 50 .
* Another 30 points will be awarded for passing the test set satisfying the condition: 1 \leq |T| \leq 10^3.

Input

The input is given from Standard Input in the following format:


T

The input only consists of T on one line.

Output

Print the maximum number of elements inS .

Examples

Input

abcabc


Output

3


Input

abracadabra


Output

7


Input

abcbabbcabbc


Output

8


Input

bbcacbcbcabbabacccbbcacbaaababbacabaaccbccabcaabba


Output

44
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using uint=unsigned int;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

void No(){
	cout<<"No"<<endl;
	exit(0);
}

template<class T>
void chmax(T& a,T b){
	a=max(a,b);
}

template<class T>
void chmin(T& a,T b){
	a=min(a,b);
}

template<class T>
void ResetVector(vector<T>& v,int n,const T& t){
	v.clear();
	v.resize(n,t);
}

const int Nmax=114514;
struct SuffixArray{
	vi sa,as,lcp;
};
namespace SA_IS{
	int bucket[Nmax];
	template <class T>
	void CreateBeginBucket(const T* data, int size, int maxVal){
		REP(i, maxVal + 1) bucket[i] = 0;
		REP(i, size) bucket[(int)data[i]]++;
		int sum = 0;
		REP(i, maxVal + 1){ bucket[i] += sum; swap(bucket[i], sum); }
	}
	 
	template <class T>
	void CreateEndBucket(const T* data, int size, int maxVal){
		REP(i, maxVal + 1) bucket[i] = 0;
		REP(i, size) bucket[(int)data[i]]++;
		int sum = 0;
		REP(i, maxVal + 1){ sum += bucket[i]; bucket[i] = sum; }
	}
	 
	template<class T>
	void InducedSort(const T* data, int size, int* SA, int maxVal, bool* isL){
		CreateBeginBucket(data, size, maxVal);
		REP(i, size) if (SA[i] > 0 && isL[SA[i] - 1]) SA[bucket[(int)data[SA[i] - 1]]++] = SA[i] - 1;
	}
	 
	template<class T>
	void InvertInducedSort(const T* data, int size, int* SA, int maxVal, bool* isL){
		CreateEndBucket(data, size, maxVal);
		for (int i = size - 1; i >= 0; --i) if (SA[i] > 0 && !isL[SA[i] - 1]) SA[--bucket[(int)data[SA[i] - 1]]] = SA[i] - 1;
	}
	 
	template <class T>
	void DBGOUT(const T* sa, int size){
		REP(i, size) printf("%d ", int(sa[i]));
		printf("\n");
	}
	 
	template<class T>
	void SA_IS(const T* data, int size, int* SA, int maxVal, bool* isL){
		REP(i, size) SA[i] = -1;
	#define isLMS(x) (x>0 && isL[x-1] && !isL[x])
		isL[size - 1] = false;
		for (int i = size - 2; i >= 0; i--) isL[i] = data[i] > data[i + 1] || (data[i] == data[i + 1] && isL[i + 1]);
		CreateEndBucket(data, size, maxVal);
		FOR(i, 1, size) if (isLMS(i)) SA[--bucket[(int)data[i]]] = i;
		InducedSort(data, size, SA, maxVal, isL);
		InvertInducedSort(data, size, SA, maxVal, isL);
	 
		int c = 0;
		REP(i, size) if (isLMS(SA[i])) SA[c++] = SA[i];
		FOR(i, c, size) SA[i] = -1;
	 
		int idx = -1;
		int prev = -1;
		REP(i, c){
			bool diff = false;
			REP(d, size){
				if (prev == -1 || data[SA[i] + d] != data[prev + d] || isL[SA[i] + d] != isL[prev + d]){
					diff = true;
					break;
				}
				else if (d > 0 && isLMS(SA[i] + d)) break;
			}
			if (diff){ idx++; prev = SA[i]; }
			SA[c + SA[i] / 2] = idx;
		}
		int j = size;
		for (int i = size - 1; i >= c; i--) if (SA[i] >= 0) SA[--j] = SA[i];
	 
		int* nxdata = SA + size - c;
		int* nxsa = SA;
		if (c == idx + 1) REP(i, c) nxsa[nxdata[i]] = i;
		else SA_IS(nxdata, c, nxsa, idx, isL + size);
	 
		j = c;
		for (int i = size - 1; i >= 1; i--) if (isLMS(i)) nxdata[--j] = i;
		REP(i, c) nxsa[i] = nxdata[nxsa[i]];
		FOR(i, c, size) SA[i] = -1;
		CreateEndBucket(data, size, maxVal);
		for (int i = c - 1; i >= 0; i--) swap(nxsa[i], SA[--bucket[(int)data[nxsa[i]]]]);
		InducedSort(data, size, SA, maxVal, isL);
		InvertInducedSort(data, size, SA, maxVal, isL);
	#undef isLMS
	}
	 
	bool isLPool[Nmax * 2];
	template<class T>
	void SA_IS(const T* data, int size, int* SA){
		int mv = 0;
		REP(i, size) if (mv < data[i]) mv = data[i];
		SA_IS(data, size, SA, mv, isLPool);
	}
	 
	int sa[Nmax],as[Nmax],lcp[Nmax];
	template<class T>
	void CreateLCP(const T* data, int size){
		REP(i,size) as[sa[i]]=i;
		int same=0;
		REP(i,size){
			if(as[i]<size-1){
				int j=sa[as[i]+1];
				while(i+same<size&&j+same<size&&data[i+same]==data[j+same])
					same++;
			}
			lcp[as[i]]=same;
			same=max(same-1,0);
		}
	}
	
	//last element should be 0(as a sentinel)
	template<class T>
	SuffixArray BuildSA(const T* data,int n){
		fill(bucket,bucket+n,0);
		fill(isLPool,isLPool+2*n,false);
		fill(sa,sa+n,0);
		fill(as,as+n,0);
		fill(lcp,lcp+n,0);
		SA_IS(data,n,sa);
		CreateLCP(data,n);
		return SuffixArray{vi(sa,sa+n),vi(as,as+n),vi(lcp,lcp+n)};
	}
}

char str[Nmax];
int main(){
	scanf("%s",str);
	int n=strlen(str);
	SuffixArray sa=SA_IS::BuildSA(str,n+1);
	vi del(n+1,0);
	FOR(i,1,n)
		del[sa.lcp[i]]++;
	int ans=0,w=0;
	for(int i=n;i>=1;i--){
		w+=del[i];
		chmax(ans,n-i+1-w);
	}
	cout<<ans<<endl;
}
