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 <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>

namespace {
template <typename Iterator, typename T>
void induced_sort(Iterator start, Iterator end, T lower, T higher, std::vector<bool> &is_s, std::vector<int> count_ls, std::vector<int> &sto)
{
	int n = end - start, k = higher - lower;

	for (int i = 0; i < k; ++i) count_ls[i * 2 + 1] = count_ls[i * 2 + 2];
	if (!is_s[n - 1]) sto[count_ls[(int)(*(end - 1) - lower) * 2]++] = n - 1; // for $
	for (int i = 1; i <= n; ++i) if (sto[i] > 0 && !is_s[sto[i] - 1]) {
		sto[count_ls[(int)(*(start + sto[i] - 1) - lower) * 2]++] = sto[i] - 1;
	}
	for (int i = 0; i < n; ++i) if (sto[i] >= 0 && is_s[sto[i]]) {
		sto[i] = -1;
	}
	for (int i = n; i >= 1; --i) if (sto[i] > 0 && is_s[sto[i] - 1]) {
		sto[--count_ls[(int)(*(start + sto[i] - 1) - lower) * 2 + 1]] = sto[i] - 1;
	}
}
template <typename Iterator>
bool compare_lms(Iterator start, std::vector<int> &lms_idx, int i, int j)
{
	do {
		if (*(start + i) != *(start + j)) return false;
		++i; ++j;
	} while (lms_idx[i] == -1 && lms_idx[j] == -1);
	return lms_idx[i] != -1 && lms_idx[j] != -1;
}
template <typename Iterator, typename T>
std::vector<int> sais(Iterator start, Iterator end, T lower, T higher)
{
	// [start, end) [lower, higher)
	int n = end - start, k = higher - lower;
	if (n == 0) return{ 0 };
	if (n == 1) return{ 1, 0 };
	std::vector<bool> is_s(n + 1, false);
	is_s[n] = true;
	for (int i = n - 1; i != 0; --i) {
		if (*(start + i - 1) < *(start + i)) is_s[i - 1] = true;
		else if (*(start + i - 1) == *(start + i)) is_s[i - 1] = is_s[i];
	}

	std::vector<int> count_ls(2 * k + 1, 0);
	count_ls[0] = 1;
	for (Iterator it = start; it != end; ++it) {
		if (is_s[it - start]) ++count_ls[(int)(*it - lower) * 2 + 2];
		else ++count_ls[(int)(*it - lower) * 2 + 1];
	}
	for (int i = 1; i <= 2 * k; ++i) count_ls[i] += count_ls[i - 1];

	std::vector<int> lms_store(k, 0);
	for (int i = 0; i < k; ++i) lms_store[i] = count_ls[i * 2 + 2];
	std::vector<int> vec_is(n + 1, -1), lms_idx(n, -1);
	int n_lms = 0;
	for (int i = 1; i < n; ++i) {
		if (is_s[i] && !is_s[i - 1]) { // a[i] is LMS
			vec_is[--lms_store[(int)(*(start + i) - lower)]] = i;
			lms_idx[i] = n_lms++;
		}
	}

	induced_sort(start, end, lower, higher, is_s, count_ls, vec_is);

	std::vector<int> nxt_str(n_lms, 0); int ord = -1, last = -1;
	for (int i = 1; i <= n; ++i) {
		int p = vec_is[i];
		if (lms_idx[p] != -1) {
			if (ord == -1 || !compare_lms(start, lms_idx, p, last)) ++ord;
			nxt_str[lms_idx[p]] = ord;
			last = p;
		}
	}

	std::vector<int> sa_sub = sais(nxt_str.begin(), nxt_str.end(), 0, ord + 1);
	for (int i = 0; i < k; ++i) lms_store[i] = count_ls[i * 2 + 2];
	for (int i = 1; i <= n; ++i) vec_is[i] = -1;
	n_lms = 0;
	for (int i = 1; i < n; ++i) {
		if (is_s[i] && !is_s[i - 1]) { // a[i] is LMS
			lms_idx[n_lms++] = i;
		}
	}
	for (int i = n_lms; i >= 1; --i) {
		int p = lms_idx[sa_sub[i]];
		vec_is[--lms_store[(int)(*(start + p) - lower)]] = p;
	}
	induced_sort(start, end, lower, higher, is_s, count_ls, vec_is);
	vec_is[0] = n;
	return vec_is;
}
std::vector<int> compute_sa_rev(const std::vector<int> &sa)
{
	std::vector<int> sa_rev(sa.size(), -1);
	for (int i = 0; i < sa.size(); ++i) sa_rev[sa[i]] = i;
	return sa_rev;
}
template <typename Iterator>
std::vector<int> compute_lcp(Iterator start, Iterator end, const std::vector<int> &sa, const std::vector<int> &sa_rev)
{
	int h = 0, n = end - start, j;
	std::vector<int> ret(n, -1);
	for (int i = 0; i < n; ++i) {
		for (int j = sa[sa_rev[i] - 1]; j + h < n && i + h < n && *(start + j + h) == *(start + i + h); ++h);
		ret[sa_rev[i] - 1] = h;
		if (h > 0) --h;
	}
	return ret;
}
class substring_info
{
public:
	substring_info() : lcp_seg_(nullptr), size_(0) {}

	// lower, higher should specify that each character is within the range [lower, higher).
	template <typename Iterator, typename T>
	substring_info(Iterator start, Iterator end, T lower, T higher)
	{
		len_ = end - start;
		std::vector<int> sa = sais(start, end, lower, higher);
		sa_rev_ = compute_sa_rev(sa);
		std::vector<int> lcp = compute_lcp(start, end, sa, sa_rev_);
		for (size_ = 1; size_ < lcp.size(); size_ <<= 1);

		lcp_seg_ = new int[size_ * 2];
		for (int i = 0; i < size_; ++i) {
			if (i < lcp.size()) lcp_seg_[i + size_] = lcp[i];
			else lcp_seg_[i + size_] = 0x7fffffff;
		}
		for (int i = size_ - 1; i >= 1; --i) lcp_seg_[i] = std::min(lcp_seg_[i * 2], lcp_seg_[i * 2 + 1]);
	}
	~substring_info() { delete[] lcp_seg_; }

	// Returns the length of the longest common prefix of substrings S[p..] and S[q..]
	int substring_common_prefix(int p, int q)
	{
		if (p == q) return len_ - p;
		int pl = sa_rev_[p], ql = sa_rev_[q];
		if (pl > ql) std::swap(pl, ql);
		return range_min(pl, ql);
	}

	// Compare substrings S[p...(p+l)] and S[q...(q+l)].
	// -1: the latter is larger.
	// 0 : both are equal.
	// 1 : the former is larger.
	int compare_substring(int p, int q, int l)
	{
		if (p == q) return 0;
		int pl = sa_rev_[p], ql = sa_rev_[q];
		int ans = (pl < ql) ? -1 : 1;
		if (pl > ql) std::swap(pl, ql);
		if (range_min(pl, ql) >= l) return 0;
		return ans;
	}
private:
	int range_min(int p, int q)
	{
		p += size_; q += size_;
		int ret = 0x7fffffff;
		while (p != q) {
			if (p & 1) ret = std::min(ret, lcp_seg_[p++]);
			if (q & 1) ret = std::min(ret, lcp_seg_[--q]);
			p >>= 1; q >>= 1;
		}
		return ret;
	}
	std::vector<int> sa_rev_;
	int *lcp_seg_;
	int len_, size_;
};
}

char S[101010];
int L;

int retr[101010];

int main()
{
	scanf("%s", S);
	L = strlen(S);

	auto sa = sais((char*)S, S + L, 'a', (char)('z' + 1));
	auto rev = compute_sa_rev(sa);
	auto lcp = compute_lcp(S, S + L, sa, rev);
	for (int i = 0; i < lcp.size(); ++i) {
		retr[lcp[i] + 1]++;
	}

	int ans = 0, tmp = 0;
	for (int k = 1; k <= L; ++k) {
		tmp += retr[k];
		ans = max(ans, tmp - k + 1);
	}
	printf("%d\n", ans);
	return 0;
}
