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>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
const int MAXLEN = (int)2e5 + 5;

char s[MAXLEN];
int SA[MAXLEN], cnt[MAXLEN], ary1[MAXLEN], ary2[MAXLEN];
int *Rank, *Height;


inline bool cmp(int *r, int a, int b, int l) {
    return r[a] == r[b] && r[a + l] == r[b + l];
}

void make_suffix_array(int MSIZE, int len) {
    int p, *x, *y, *tmp, i, j, k;
    x = ary1; y = ary2;
    memset(cnt, 0, sizeof(int) * MSIZE);
    for (i = 0; i < len; i++) cnt[x[i] = s[i]]++;
    for (i = 1; i < MSIZE; i++) cnt[i] += cnt[i - 1];
    for (i = len - 1; i >= 0; i--) SA[--cnt[x[i]]] = i;
    for (j = p = 1; p < len; j <<= 1, MSIZE = p) {
        for (p = 0, i = len - j; i < len; i++) y[p++] = i;
        for (i = 0; i < len; i++) {
            if (SA[i] >= j) y[p++] = SA[i] - j;
        }
        memset(cnt, 0, sizeof(int) * MSIZE);
        for (i = 0; i < len; i++) cnt[x[y[i]]]++;
        for (i = 1; i < MSIZE; i++) cnt[i] += cnt[i - 1];
        for (i = len - 1; i >= 0; i--) SA[--cnt[x[y[i]]]] = y[i];
        tmp = x; x = y; y = tmp;
        x[SA[0]] = 0;
        for (i = p = 1; i < len; i++) {
            x[SA[i]] = cmp(y, SA[i - 1], SA[i], j) ? p - 1 : p++;
        }
    }
    Rank = x;
    Height = y;
    for (i = k = 0; i < len - 1; i++) {
        if (k > 0) k--;
        j = SA[Rank[i] - 1];
        while (s[i + k] == s[j + k]) k++;
        Height[Rank[i]] = k;
    }
}
int dp[SIZE];
int main(){
    RS(s);
    int n=LEN(s);
    make_suffix_array(128,n+1);
    REP(i,n){
        if(Height[Rank[i]]+1<=n-i){
            dp[Height[Rank[i]]+1]++;
            dp[n-i+1]--;
        }
    }
    int an=0;
    REPP(i,1,n+1){
        dp[i]+=dp[i-1];
        an=max(an,dp[i]);
    }
    printf("%d\n",an);
    return 0;
}
