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;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
char s[125252];

typedef unsigned int Hash1;
typedef unsigned short Hash2;
struct Hash{
  Hash1 first;
  Hash2 second;
  Hash():first(0),second(0){}
  Hash(Hash1 first,Hash2 second):first(first),second(second){}
};
bool operator==(const Hash &a,const Hash &b){
  return a.first==b.first && a.second==b.second;
}
const Hash1 b1 = 29;
const Hash2 b2 = 29;
const Hash2 m2 = 127;
const int MAX = 100001;
Hash hsh[MAX];
Hash bpow[MAX];

struct HashHash {
  size_t operator()(const Hash &yey) const {
    hash<int> hasher;
    return hasher((int)yey.first)^hasher((int)yey.second);
  }
};

unordered_set<Hash,HashHash> S;
int calc(int x){
  S.clear();
  REP(i,n-x+1){
    // substr
    int l = i;
    int r = l+x;
    Hash h(0,0);
    h.first += hsh[l].first;
    h.second+= hsh[l].second;
    h.first *= bpow[x].first;
    h.second*= bpow[x].second;
    // mod & negative
    h.first = -h.first;
    h.second= m2 - h.second%m2;
    h.first += hsh[r].first;
    h.second+= hsh[r].second;
    h.second= h.second%m2;
    S.insert(h);
  }
  return S.size();
}

int main(){
  scanf("%s",s);
  n = strlen(s);
  // create hash
  REP(i,n){
    int id = s[i]-'a';
    hsh[i+1].first = hsh[i].first*b1 + (Hash1)id;
    hsh[i+1].second= (hsh[i].second*b2+ (Hash2)id)%m2;
  }
  // base pow
  bpow[0] = Hash(1,1);
  REP(i,n){
    bpow[i+1].first = bpow[i].first*b1;
    bpow[i+1].second= bpow[i].second*b2%m2;
  }
  // go
  int low = 1, high = n;
  while(low+2<high){
    int ml = (low+high)/2;
    int mh = ml+1;
    if(calc(ml)<calc(mh)){
      low = ml;
    }else{
      high = mh;
    }
  }
  int ans = 0;
  FOR(i,low,high+1)CHMAX(ans,calc(i));
  printf("%d\n",ans);
  return 0;
}
