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
#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
#define inf 1000000007
#define mod 1000000007
#define x first
#define y second
#define pi acos(-1.0)
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
//#define dprintf(...) 
#define hash _hash
#define next _next
//#define dprintf(...) fprintf(outFile,__VA_ARGS__)
 
#define FOREACH(it,x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define ull unsigned long long
#define ll long long
#define N 100010
 
template <class T,class U>inline void Max(T &a,U b){if(a<b)a=b;}
template <class T,class U>inline void Min(T &a,U b){if(a>b)a=b;}
 
//FILE* outFile;
inline void add(int &a,int b){a+=b;while(a>=mod)a-=mod;}


int pow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*(ll)a%mod;
        a=(ll)a*a%mod;b>>=1;
    }
    return ans;
}

char s[N];
const int mo1=1e9+9;
int n,h[N],q[N],h1[N],q1[N];
int cal(int i,int j,int h[],int q[],int mo){return (h[j]-1LL*h[i]*q[j-i]%mo+mo)%mo;}
struct node{
	int v,v1,next;
}g[N];
const int mo=233333;
int head[mo],cnt,dp[N];
int add1(int v,int v1){
	int k=v%mo;
	for(int i=head[k];~i;i=g[i].next){
		if(g[i].v==v&&g[i].v1==v1)return 0;
	}
	g[cnt]={v,v1,head[k]};head[k]=cnt++;
	return 1;
}
int cal(int d){
	if(dp[d]!=0)return dp[d];
	cnt=0;
	memset(head,-1,sizeof(head));
	int ans=0;
	rep(i,0,n-d+1){
		int k=cal(i,i+d,h,q,mod),k1=cal(i,i+d,h1,q1,mo1);
		ans+=add1(k,k1);
	}
	return dp[d]=ans;
}
int main(){
    int T,i,j,k,ca=0,K,m;
    //cout<<setprecision(10)<<fixed;
    scanf("%s",s);n=strlen(s);q[0]=q1[0]=1;
    rep(i,0,n)q[i+1]=q[i]*29LL%mod,h[i+1]=(h[i]*29LL+s[i])%mod,q1[i+1]=q1[i]*37LL%mo1,h1[i+1]=(h1[i]*37LL+s[i])%mo1;
    int l=1,r=n,ans=1;
    while(l+100<r){
    	int x=(2*l+r)/3,y=(2*r+l)/3;
    	int p=cal(x),q=cal(y);
    	if(cal(x)<=cal(y))Max(ans,q),l=x+1;else Max(ans,p),r=y-1;
    }
    rep(i,l,r+1)Max(ans,cal(i));
    printf("%d\n",ans);
    return 0;
}

