Problem: Xenia the coder went to The Olympiad of Informatics and got a string problem. Unfortunately, Xenia isn't fabulous in string algorithms. Help her solve the problem.

String s is a sequence of characters s1s2... s|s|, where record |s| shows the length of the string. 

Substring s[i... j] of string s is string sisi + 1... sj.

String s is a Gray string, if it meets the conditions:

  * the length of string |s| is odd; 
  * character <image> occurs exactly once in the string; 
  * either |s| = 1, or substrings <image> and <image> are the same and are Gray strings. 



For example, strings "abacaba", "xzx", "g" are Gray strings and strings "aaa", "xz", "abaxcbc" are not.

The beauty of string p is the sum of the squares of the lengths of all substrings of string p that are Gray strings. In other words, consider all pairs of values i, j (1 ≤ i ≤ j ≤ |p|). If substring p[i... j] is a Gray string, you should add (j - i + 1)2 to the beauty.

Xenia has got string t consisting of lowercase English letters. She is allowed to replace at most one letter of the string by any other English letter. The task is to get a string of maximum beauty.

Input

The first line contains a non-empty string t (1 ≤ |t| ≤ 105). String t only consists of lowercase English letters.

Output

Print the sought maximum beauty value Xenia can get.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

zzz


Output

12


Input

aba


Output

12


Input

abacaba


Output

83


Input

aaaaaa


Output

15

Note

In the first test sample the given string can be transformed into string p = "zbz". Such string contains Gray strings as substrings p[1... 1], p[2... 2], p[3... 3] и p[1... 3]. In total, the beauty of string p gets equal to 12 + 12 + 12 + 32 = 12. You can't obtain a more beautiful string.

In the second test case it is not necessary to perform any operation. The initial string has the maximum possible beauty.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int LEN = 100100 * 3;
int r[LEN], sa[LEN];
int wa[LEN], wb[LEN], wv[LEN], ss[LEN];
int c0(int *r, int a, int b) {
  return r[a] == r[b] && r[a + 1] == r[b + 1] && r[a + 2] == r[b + 2];
}
int c12(int k, int *r, int a, int b) {
  if (k == 2) return r[a] < r[b] || (r[a] == r[b] && c12(1, r, a + 1, b + 1));
  return r[a] < r[b] || (r[a] == r[b] && wv[a + 1] < wv[b + 1]);
}
void sort(int *r, int *a, int *b, int n, int m) {
  for (int i = 0; i < n; i++) wv[i] = r[a[i]];
  for (int i = 0; i < m; i++) ss[i] = 0;
  for (int i = 0; i < n; i++) ss[wv[i]]++;
  for (int i = 1; i < m; i++) ss[i] += ss[i - 1];
  for (int i = n - 1; i >= 0; i--) b[--ss[wv[i]]] = a[i];
}
void DC3(int *r, int *sa, int n, int m) {
  int i, j, p;
  int *san = sa + n, *rn = r + n;
  int ta = 0, tb = (n + 1) / 3, tbc = 0;
  r[n] = r[n + 1] = 0;
  for (i = 0; i < n; i++)
    if (i % 3 != 0) wa[tbc++] = i;
  sort(r + 2, wa, wb, tbc, m);
  sort(r + 1, wb, wa, tbc, m);
  sort(r, wa, wb, tbc, m);
  for (p = 1, rn[((wb[0]) / 3 + ((wb[0]) % 3 == 1 ? 0 : tb))] = 0, i = 1;
       i < tbc; i++)
    rn[((wb[i]) / 3 + ((wb[i]) % 3 == 1 ? 0 : tb))] =
        c0(r, wb[i - 1], wb[i]) ? p - 1 : p++;
  if (p < tbc)
    DC3(rn, san, tbc, p);
  else
    for (i = 0; i < tbc; i++) san[rn[i]] = i;
  for (i = 0; i < tbc; i++)
    if (san[i] < tb) wb[ta++] = san[i] * 3;
  if (n % 3 == 1) wb[ta++] = n - 1;
  sort(r, wb, wa, ta, m);
  for (i = 0; i < tbc; i++)
    wv[wb[i] = ((san[i]) < tb ? (san[i]) * 3 + 1 : ((san[i]) - tb) * 3 + 2)] =
        i;
  for (i = 0, j = 0, p = 0; i < ta && j < tbc; p++)
    sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
  for (; i < ta; p++) sa[p] = wa[i++];
  for (; j < tbc; p++) sa[p] = wb[j++];
}
int rnk[100100], lcp[18][100100];
void calc_LCP(int *r, int *sa, int n) {
  int k = 0;
  for (int i = 0; i < n; i++) rnk[sa[i]] = i;
  for (int i = 0; i < n - 1; lcp[0][rnk[i++]] = k) {
    if (k) k--;
    for (int j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; k++)
      ;
  }
  for (int j = 1; j < 18; j++) {
    for (int i = (1 << j); i < n; i++) {
      lcp[j][i] = min(lcp[j - 1][i], lcp[j - 1][i - (1 << (j - 1))]);
    }
  }
}
char s[100100];
int n, B;
bool f[100100][18];
int can[100100][18];
int val[100100][18];
int calc(int x, int y) {
  x = rnk[x];
  y = rnk[y];
  if (x > y) swap(x, y);
  int i = 0;
  while (x + (1 << i) <= y) i++;
  i--;
  return min(lcp[i][y], lcp[i][x + (1 << i)]);
}
long long ans, cur[100100];
int q[100100 * 20];
void run() {
  for (int i = 0; i < n; i++) f[i][1] = 1, val[i][1] = 1 << (s[i] - 'a');
  ans = n;
  for (int j = 2; j <= B; j++) {
    for (int i = 0; i < n; i++) {
      if (i + (1 << j) - 1 <= n) {
        int k = s[i + (1 << (j - 1)) - 1] - 'a';
        if (f[i][j - 1] && !(val[i][j - 1] & (1 << k))) {
          if (f[i + (1 << (j - 1))][j - 1] &&
              calc(i, i + (1 << (j - 1))) >= (1 << (j - 1)) - 1) {
            f[i][j] = 1;
            val[i][j] = val[i][j - 1] | (1 << k);
            ans += 1LL * ((1 << j) - 1) * ((1 << j) - 1);
            for (int t = 0; t < (1 << j) - 1; t++)
              cur[t + i] += 1LL * ((1 << j) - 1) * ((1 << j) - 1);
          }
        }
      }
    }
  }
  long long curans = ans;
  if (B < 2) return;
  for (int i = 0; i < n; i++) {
    long long mx = 0;
    for (int t = 0; t < 26; t++)
      if (s[i] - 'a' != t) {
        long long tp = 0;
        int hd = 0, tl = 0;
        q[tl++] = i;
        for (int d = 2; d <= B; d++) {
          int len = tl - hd;
          while (len--) {
            int pos = q[hd++], nxt = pos + (1 << (d - 1)),
                cen = pos + (1 << (d - 2)) - 1;
            if (nxt < n && f[nxt][d - 1] &&
                !(val[nxt][d - 1] & (1 << (s[nxt - 1] - 'a')))) {
              bool ok = 0;
              if (i == cen) {
                if (t == s[nxt + (1 << (d - 2)) - 1] - 'a' &&
                    calc(pos, nxt) >= (1 << (d - 2)) - 1)
                  ok = 1;
              } else if (i < cen) {
                if (calc(pos + (1 << (d - 2)) - 1, nxt + (1 << (d - 2)) - 1) >=
                    (1 << (d - 2)))
                  ok = 1;
              } else {
                if (calc(pos, nxt) >= (1 << (d - 2))) ok = 1;
              }
              if (ok) {
                q[tl++] = pos;
                tp += 1LL * ((1 << d) - 1) * ((1 << d) - 1);
              }
            }
            nxt = pos - (1 << (d - 1));
            if (nxt >= 0 && f[nxt][d - 1] &&
                !(val[nxt][d - 1] & (1 << (s[pos - 1] - 'a')))) {
              bool ok = 0;
              if (i == cen) {
                if (t == s[nxt + (1 << (d - 2)) - 1] - 'a' &&
                    calc(pos, nxt) >= (1 << (d - 2)) - 1)
                  ok = 1;
              } else if (i < cen) {
                if (calc(pos + (1 << (d - 2)) - 1, nxt + (1 << (d - 2)) - 1) >=
                    (1 << (d - 2)))
                  ok = 1;
              } else {
                if (calc(pos, nxt) >= (1 << (d - 2))) ok = 1;
              }
              if (ok) {
                q[tl++] = nxt;
                tp += 1LL * ((1 << d) - 1) * ((1 << d) - 1);
              }
            }
            nxt = i - (1 << (d - 1)) + 1;
            if (nxt >= 0 && f[nxt][d - 1] && f[i + 1][d - 1] &&
                !(val[nxt][d - 1] & (1 << (t)))) {
              if (calc(nxt, i + 1) >= (1 << (d - 1)) - 1) {
                q[tl++] = nxt;
                tp += 1LL * ((1 << d) - 1) * ((1 << d) - 1);
              }
            }
          }
        }
        mx = max(mx, tp);
      }
    ans = max(ans, curans - cur[i] + mx);
  }
}
int main() {
  gets(s);
  n = strlen(s);
  for (int i = 0; i < n; i++) r[i] = s[i];
  r[n] = 0;
  DC3(r, sa, n + 1, 256);
  calc_LCP(r, sa, n + 1);
  B = 1;
  while ((1 << B) - 1 <= n) B++;
  B--;
  run();
  printf("%I64d\n", ans);
  return 0;
}