2026-05-11(#12)：如同谎言般闪闪发光的一等星

#include <bits/stdc++.h>
#define uint unsigned int
using namespace std;
constexpr int N = 1e5 + 5;

uint n;
int f[2][N];
int g[2][N]; // = max(f[ <= i][ <= j])
int rk[N]; // 开头为 x 的东西的排名

struct Fenwick {
    int C[N];
    void clear() { fill(C + 1, C + n + 1, -1e9); }
    void add(int x, int k) { for (; x <= n; x += x & -x) C[x] = max(C[x], k); }
    int qmax(int x) const { int r = -1e9; for (; x; x -= x & -x) r = max(r, C[x]); return r; }
} F;


void solve() {
    string a; cin >> a; n = a.length();

    vector<int> lst;
    for (int i = n - 1; i >= 0; --i) lst.emplace_back(i);

    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);

    const int B = ceil(sqrt(n * 2)) + 5;

    for (int j = 0; j < B; ++j) {
        const int len = j;
        vector<int> pos[10];
        for (int i : lst)
            pos[a[i] - '0'].emplace_back(i);
        lst.clear();
        int tot = 0;
        for (int k = 0; k < 10; ++k)
            for (const int x : pos[k]) {
                if (x) lst.emplace_back(x - 1);
                rk[x] = ++tot;
            }

        F.clear();
        for (int i = j; i < n; ++i) {
            f[j & 1][i] = 1;

            if (!(j && a[i - j] == '0')) {
                if (i >= j + 1) f[j & 1][i] = max(f[j & 1][i], g[j - 1 & 1][i - j - 1] + 1); // i - j - 1 >= j - 1
            }

            f[j & 1][i] = max(f[j & 1][i], F.qmax(rk[i - j] - 1) + 1);

            if (i - j >= j) F.add(rk[i - j - j], f[j & 1][i - j]);
        }

        for (int i = 0; i < n; ++i) {
            g[j & 1][i] = f[j & 1][i];
            if (i) g[j & 1][i] = max(g[j & 1][i], g[j & 1][i - 1]);
            if (j) g[j & 1][i] = max(g[j & 1][i], g[j - 1 & 1][i]);
        }
    }

    cout << g[B - 1 & 1][n - 1] << '\n';
}

int main(void) {
    ios::sync_with_stdio(false);
    uint T; cin >> T;
    while (T--) solve();
    return 0;
}