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 <vector>
#include <string>
#include <iostream>
namespace lc {
class SuffixArray {
private:
	std::vector<int> m_suffix_array;
	template <bool End, class T>
	std::vector<int> compute_buckets(const T *s, int n, int k) const {
		std::vector<int> buckets(k);
		for(int i = 0; i < n; ++i){ ++buckets[s[i]]; }
		for(int i = 0, sum = 0; i < k; ++i){
			sum += buckets[i];
			buckets[i] = (End ? sum : (sum - buckets[i]));
		}
		return buckets;
	}
	template <class T>
	void induce_sa_l(
		int *sa, const T *s, int n, int k,
		const std::vector<bool> &types) const
	{
		std::vector<int> buckets(compute_buckets<false>(s, n, k));
		for(int i = 0; i < n; ++i){
			const int j = sa[i] - 1;
			if(j >= 0 && !types[j]){ sa[buckets[s[j]]++] = j; }
		}
	}
	template <class T>
	void induce_sa_s(
		int *sa, const T *s, int n, int k,
		const std::vector<bool> &types) const
	{
		std::vector<int> buckets(compute_buckets<true>(s, n, k));
		for(int i = n - 1; i >= 0; --i){
			const int j = sa[i] - 1;
			if(j >= 0 && types[j]){ sa[--buckets[s[j]]] = j; }
		}
	}
	bool is_lms(const std::vector<bool> &types, int i) const {
		return i > 0 && !types[i - 1] && types[i];
	}
	template <class T>
	void sa_is(int *sa, const T *s, int n) const {
		std::vector<bool> types(n);
		types[n - 1] = true;
		for(int i = n - 2; i >= 0; --i){
			types[i] = (s[i] != s[i + 1] ? s[i] < s[i + 1] : types[i + 1]);
		}
		const int k = static_cast<int>(*std::max_element(s, s + n)) + 1;
		std::vector<int> buckets(compute_buckets<true>(s, n, k));
		for(int i = 0; i < n; ++i){ sa[i] = -1; }
		for(int i = 1; i < n; ++i){
			if(is_lms(types, i)){ sa[--buckets[s[i]]] = i; }
		}
		induce_sa_l(sa, s, n, k, types);
		induce_sa_s(sa, s, n, k, types);
		int m = 0;
		for(int i = 0; i < n; ++i){
			if(is_lms(types, sa[i])){ sa[m++] = sa[i]; }
		}
		for(int i = m; i < n; ++i){ sa[i] = -1; }
		int num_names = 0, prev = -1;
		for(int i = 0; i < m; ++i){
			int p = sa[i];
			bool diff = false;
			for(int d = 0; d < n; ++d){
				const int l = p + d, r = prev + d;
				if(prev < 0 || s[l] != s[r] || types[l] != types[r]){
					diff = true;
					break;
				}else if(d > 0 && (is_lms(types, l) || is_lms(types, r))){
					break;
				}
			}
			if(diff){
				++num_names;
				prev = p;
			}
			p = (p - (p & 1)) / 2;
			sa[m + p] = num_names - 1;
		}
		for(int i = n - 1, j = n - 1; i >= m; --i){
			if(sa[i] >= 0){ sa[j--] = sa[i]; }
		}
		int *reduced_s = sa + n - m;
		if(num_names < m){
			sa_is(sa, reduced_s, m);
		}else{
			for(int i = 0; i < m; ++i){ sa[reduced_s[i]] = i; }
		}
		buckets = compute_buckets<true>(s, n, k);
		for(int i = 1, j = 0; i < n; ++i){
			if(is_lms(types, i)){ reduced_s[j++] = i; }
		}
		for(int i = 0; i < m; ++i){ sa[i] = reduced_s[sa[i]]; }
		for(int i = m; i < n; ++i){ sa[i] = -1; }
		for(int i = m - 1; i >= 0; --i){
			const int j = sa[i];
			sa[i] = -1;
			sa[--buckets[s[j]]] = j;
		}
		induce_sa_l(sa, s, n, k, types);
		induce_sa_s(sa, s, n, k, types);
	}
	template <class T>
	std::vector<int> sa_is(const T &s) const {
		if(s.size() == 0){ return std::vector<int>(1); }
		const int n = s.size() + 1;
		std::vector<int> vs(n);
		for(int i = 0; i + 1 < n; ++i){ vs[i] = s[i]; }
		std::vector<int> sa(n);
		sa_is(sa.data(), vs.data(), n);
		return sa;
	}
public:
	template <class T>
	explicit SuffixArray(const T &s)
		: m_suffix_array(sa_is(s))
	{ }
	size_t size() const { return m_suffix_array.size(); }
	int operator[](int i) const { return m_suffix_array[i]; }
};
}
namespace lc {
template <class T>
std::vector<int> longest_common_prefix(const T &s, const SuffixArray &sa){
	const int n = sa.size();
	std::vector<int> vs(n), isa(n), lcp(n - 1);
	for(int i = 0; i + 1 < n; ++i){ vs[i] = s[i]; }
	for(int i = 0; i < n; ++i){ isa[sa[i]] = i; }
	int h = 0;
	for(int i = 0; i < n; ++i){
		const int j = isa[i];
		if(j > 0){
			const int k = j - 1;
			while(vs[sa[j] + h] == vs[sa[k] + h]){ ++h; }
			lcp[k] = h;
			if(h > 0){ --h; }
		}
	}
	return lcp;
}
}
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	string s;
	cin >> s;
	const int n = s.size();
	lc::SuffixArray sa(s);
	const auto lcp = longest_common_prefix(s, sa);
	vector<int> hist(n);
	for(const auto x : lcp){
		++hist[x];
	}
	int answer = 0;
	for(int i = 0, sum = 0; i < n; ++i){
		sum += hist[i];
		answer = max(answer, sum - i);
	}
	cout << answer << endl;
	return 0;
}
