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 <algorithm>
#include <climits>
#include <vector>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
 
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)n;++i)
 
// Larsson-Sadakane's Suffix array Construction: O(n (log n)^2)
struct SAComp {
  const int h, *g;
  SAComp(int h, int* g) : h(h), g(g) {}
  bool operator() (int a, int b) {
    return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a+h] < g[b+h];
  }
};
int *buildSA(char* t, int n) {
  int *g = new int[n+1], *b = new int[n+1], *v = new int[n+1];
  REP(i,n+1) v[i] = i, g[i] = t[i];
  b[0] = 0; b[n] = 0;
 
  sort(v, v+n+1, SAComp(0, g));
  for(int h = 1; b[n] != n ; h *= 2) {
    SAComp comp(h, g);
    sort(v, v+n+1, comp);
    REP(i, n) b[i+1] = b[i] + comp(v[i], v[i+1]);
    REP(i, n+1) g[v[i]] = b[i];
  }
  return v;
}
// Kasai-Lee-Arimura-Arikawa-Park's simple LCP computation: O(n)
int *buildLCP(char *t, int n, int *a) {
  int h = 0, *b = new int[n+1], *lcp = new int[n+1];
  REP(i, n+1) b[a[i]] = i;
  REP(i, n+1) {
    if (b[i]){
      for (int j = a[b[i]-1]; j+h<n && i+h<n && t[j+h] == t[i+h]; ++h);
      lcp[b[i]] = h;
    } else lcp[b[i]] = -1;
    if (h > 0) --h;
  }
  return lcp;
}
 
struct segment_tree_min {
	int n; vector<ll> v;
	segment_tree_min() {}
	segment_tree_min(int _n) {
		for (n = 1; n < _n; n *= 2);
		v = vector<ll>(n * 2 - 1, LLONG_MAX);
	}
	void set(int i, ll x) {
		int k = i + n - 1;
		v[k] = x;
		while (k > 0) {
			k = (k - 1) / 2;
			v[k] = min(v[k * 2 + 1], v[k * 2 + 2]);
		}
	}
	ll _get(int i, int j, int k, int l, int r) {
		if (r <= i || j <= l) return LLONG_MAX;
		if (i <= l && r <= j) return v[k];
		ll vl = _get(i, j, k * 2 + 1, l, (l + r) / 2);
		ll vr = _get(i, j, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
	ll get(int i, int j) { return _get(i, j, 0, 0, n); }
};
 
int N;
char S[100010];
int *sa, *lcp, *rmq, rnk[100010];
int p[100010];
segment_tree_min st;
 
int f(int i, int j) {
	if (i == j) return N - i;
	int x = rnk[i], y = rnk[j];
	if (x > y) swap(x, y);
	return st.get(x + 1, y + 1);
}
 
bool cmp(int i, int j) {
	if (f(i, j) < N - max(i, j)) return rnk[i] < rnk[j];
	int k = N - abs(i - j);
	if (i < j) j = i, i = k;
	else i = j, j = k;
	if (f(i, j) < N - max(i, j)) return rnk[i] < rnk[j];
	return false;
}

struct union_find {
	vector<int> v;
	union_find(int n) : v(n, -1) {}
	int find(int x) { return (v[x] < 0) ? x : (v[x] = find(v[x])); }
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x != y) {
			if (-v[x] < -v[y]) swap(x, y);
			v[x] += v[y]; v[y] = x;
		}
	}
	bool same(int x, int y) { return find(x) == find(y); }
	int size(int x) { return -v[find(x)]; }
};

int main() {
	scanf("%s", S);
	int N = strlen(S);
	sa = buildSA(S, N);
	lcp = buildLCP(S, N, sa);
	vector<vector<int> > v(N + 1);
	for (int i = 2; i <= N; i++)
		v[lcp[i]].push_back(i - 2);
	vector<int> a(N + 1);
	for (int i = 1; i <= N; i++)
		a[N - sa[i]] = i - 1;
	union_find uf(N);
	vector<int> unko(N);
	int ans = 0, ma = 0;
	for (int d = N; d >= 0; d--) {
		int k = uf.find(a[d]);
		unko[k]++;
		if (unko[k] == 1) ans++;
		for (int i: v[d]) {
			int x = unko[uf.find(i)], y = unko[uf.find(i + 1)];
			if (x && y) ans--;
			uf.unite(i, i + 1);
			unko[uf.find(i)] = x + y;
		}
		ma = max(ma, ans);
	}
	cout << ma << endl;
}
