#include <bits/stdc++.h>
using namespace std;

const int B = 1000;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    string t;
    cin >> t;
    int n = t.length();
    if (t.size() == 1) {
        cout << "1\n";
        return 0;
    }

    auto check = [&](const string &s) {
        int n = s.size();
        int ptr = 0;
        for (auto c : t) {
            while (ptr < n && s[ptr] != c) ++ptr;
            if (ptr == n) return false;
            ++ptr;
        }
        return true;
    };

    vector<string> S{"b", "a"};
    int c = 1;
    while (true) {
        S.push_back(S[c] + S[c - 1]);
        ++c;
        if (check(S[c])) break;
    }

    int thr = 0;
    while (thr < c && (int) S[thr + 1].size() < B) ++thr;
    
    vector<vector<int>> to(2, vector<int>(n, 0));
    for (int o = 0; o < 2; ++o) {
        const auto &s = S[thr - o];
        for (int i = 0; i < n; ++i) {
            int ptr = i;
            for (auto c : s) {
                if (c == t[ptr]) ++ptr;
                if (ptr == n) break;
            }
            to[o][i] = ptr;
            // cerr << "? " << o << " " << i << " " << ptr << endl;
        }
    }

    // cerr << "c = " << c << " " << thr << "\n";
    int m = S[c].size();
    vector<int> mark(m + 1, -1);
    int pos = 0;
    function<void(int)> dfs = [&](int i) {
        if (i <= thr) {
            mark[pos] = thr - i;
            pos += S[i].size();
            return;
        }
        dfs(i - 1), dfs(i - 2);
    }; 
    dfs(c);
    assert(pos == m);

    int ans = 1e9;
    for (int i = 0; i < m; ++i) {
        // cerr << "? " << i << endl;
        int ptr = 0, j = i;
        while (ptr < n && j < m) {
            int id = mark[j];
            if (~id) {
                int sz = S[thr - id].size();
                if (to[id][ptr] < n) {
                    j += sz;
                    ptr = to[id][ptr];
                    continue;
                }
            }
            if (t[ptr] == S[c][j]) ++ptr;
            ++j;
            // cerr << "? " << j << " " << ptr << endl;
        }
        if (ptr == n) {
            ans = min(ans, j - i);
        }
    }

    cout << ans << "\n";

    return 0;
}