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 REP(i, n) for (ll i = 0; i < ll(n); ++i)
#define RREP(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define FOR(i, m, n) for (ll i = m; i < ll(n); ++i)
#define RFOR(i, m, n) for (ll i = ll(n) - 1; i >= ll(m); --i)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

constexpr int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
constexpr int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template <class T> bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

using namespace std;
// verified: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3384713
// lcp verified: https://atcoder.jp/contests/kupc2016/submissions/4613878
class SuffixArray {
  int n;
  string str;
  vector<int> sa, rank;

  template <typename Compare>
  int binarySearch(const string& t) {
    int m = t.size();
    int lb = -1, ub = n + 1;
    while (ub - lb > 1) {
      int mid = (ub + lb) / 2;
      if (Compare()(strncmp(str.c_str() + sa[mid], t.c_str(), m), 0)) {
        lb = mid;
      }
      else {
        ub = mid;
      }
    }
    return ub;
  }

public:
  // 構築 O(n (logn)^2)
  SuffixArray(const string _s) : n(_s.size()), str(_s), sa(n + 1), rank(n + 1) {
    for (int i = 0; i <= n; i++) {
      sa[i] = i;
      rank[i] = i < n ? str[i] : -1;
    }
    vector<int> tmp(n + 1);
    for (int k = 1; k <= n; k *= 2) {
      // (rank[i], rank[i+k]), (rank[j], rank[j+k]) を比較
      auto compare_sa = [=](int i, int j) {
        if (rank[i] != rank[j])
          return rank[i] < rank[j];
        else {
          int ri = i + k <= n ? rank[i + k] : -1;
          int rj = j + k <= n ? rank[j + k] : -1;
          return ri < rj;
        }
      };
      sort(sa.begin(), sa.end(), compare_sa);
      tmp[sa[0]] = 0;
      for (int i = 1; i <= n; i++) {
        tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
      }
      for (int i = 0; i <= n; i++) {
        rank[i] = tmp[i];
      }
    }
  }
  // O(|t|logn)
  bool contain(const string& t) {
    int lb = 0, ub = n;
    while (ub - lb > 1) {
      int mid = (lb + ub) / 2;
      if (str.compare(sa[mid], t.size(), t) < 0)
        lb = mid;
      else
        ub = mid;
    }
    return str.compare(sa[ub], t.size(), t) == 0;
  }
  // 高さ配列 := 接尾辞配列における隣接要素で先頭何文字が共通しているか
  // つまり, lcp[i] = str[sa[i]..] と str[sa[i+1]..] の先頭共通文字数
  // O(n)
  vector<int> getLcp() {
    for (int i = 0; i <= n; i++) rank[sa[i]] = i;
    int h = 0;
    vector<int> lcp(n + 1);
    for (int i = 0; i < n; i++) {
      int j = sa[rank[i] - 1];
      if (h > 0) h--;
      for (; j + h < n && i + h < n; h++) {
        if (str[j + h] != str[i + h]) break;
      }
      lcp[rank[i] - 1] = h;
    }
    return lcp;
  }
  vector<int> getSa() {
    return sa;
  }
  int lowerBound(const string& t) {
    return binarySearch<less<int>>(t);
  }
  int upperBound(const string& t) {
    return binarySearch<less_equal<int>>(t);
  }
};

// 高さ配列 + セグ木 で任意の接尾辞同士で先頭共通文字数を求められる
// インデックス i,j の先頭共通文字数は rank[i]<rank[j] ならば
// min(lcp[rank[i]], lcp[rank[i]+1], ... , lcp[rank[j]-1]) に一致



int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string t;
  cin >> t;
  SuffixArray sa(t);
  auto lcp = sa.getLcp();
  cout << t.size() - *max_element(lcp.begin(), lcp.end()) << endl;
}
