#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <array>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;

#include <iterator>
#include <functional>
#include <utility>
#include <type_traits>

template<class Elem> struct vec;

template<class Iter>
struct seq_view{
    using Ref = typename std::iterator_traits<Iter>::reference;
    using Elem = typename std::iterator_traits<Iter>::value_type;
    Iter a, b;
    Iter begin() const { return a; }
    Iter end() const { return b; }
    int size() const { return (int)(b-a); }
    seq_view(Iter first, Iter last) : a(first), b(last) {}
    seq_view sort() const { std::sort(a, b); return *this; }
    Ref& operator[](int x) const { return *(a+x); }
    template<class F = std::less<Elem>, class ret = vec<int>> ret sorti(F f = F()) const {
        ret x(size()); for(int i=0; i<size(); i++) x[i] = i;
        x().sort([&](int l, int r){ return f(a[l],a[r]); });
        return x;
    }
    template<class ret = vec<Elem>> ret col() const { return ret(begin(), end()); }
    template<class ret = vec<Elem>> ret cumsum() const {
        auto res = ret(size() + 1, Elem(0));
        for(int i=0; i<size(); i++) res[i+1] = res[i] + operator[](i);
        return res;
    }
    template<class F = std::equal_to<Elem>, class ret = vec<std::pair<Elem, int>>>
    ret rle(F eq = F()) const {
        auto x = ret();
        for(auto& a : (*this)){
            if(x.size() == 0 || !eq(x[x.size()-1].first, a)) x.emp(a, 1); else x[x.size()-1].second++;
        } return x;
    }
    template<class F> seq_view sort(F f) const { std::sort(a, b, f); return *this; }
    Iter uni() const { return std::unique(a, b); }
    Iter lb(const Elem& x) const { return std::lower_bound(a, b, x); }
    Iter ub(const Elem& x) const { return std::upper_bound(a, b, x); }
    int lbi(const Elem& x) const { return lb(x) - a; }
    int ubi(const Elem& x) const { return ub(x) - a; }
    seq_view bound(const Elem& l, const Elem& r) const { return { lb(l), lb(r) }; }
    template<class F> Iter lb(const Elem& x, F f) const { return std::lower_bound(a, b, x, f); }
    template<class F> Iter ub(const Elem& x, F f) const { return std::upper_bound(a, b, x, f); }
    template<class F> Iter when_true_to_false(F f) const {
        if(a == b) return a;
        return std::lower_bound(a, b, *a,
            [&](const Elem& x, const Elem&){ return f(x); });
    }
    seq_view same(Elem x) const { return { lb(x), ub(x) }; }
    template<class F> auto map(F f) const {
        vec<decltype(f(std::declval<const typename Iter::value_type&>()))> r;
        for(auto& x : *this) r.emp(f(x));
        return r;
    }
    Iter max() const { return std::max_element(a, b); }
    Iter min() const { return std::min_element(a, b); }
    template<class F = std::less<Elem>>
    Iter min(F f) const { return std::min_element(a, b, f); }
    seq_view rev() const { std::reverse(a, b); return *this; }
};

template<class Elem>
struct vec {
public:
    using Base = typename std::vector<Elem>;
    using Iter = typename Base::iterator;
    using CIter = typename Base::const_iterator;
    using View = seq_view<Iter>;
    using CView = seq_view<CIter>;

    vec(){}
    explicit vec(int n, const Elem& value = Elem()) : a(0<n?n:0, value) {}
    template <class I2> vec(I2 first, I2 last) : a(first, last) {}
    vec(std::initializer_list<Elem> il) : a(std::move(il)) {}
    vec(Base b) : a(std::move(b)) {}
    operator Base() const { return a; }

    Iter begin(){ return a.begin(); }
    CIter begin() const { return a.begin(); }
    Iter end(){ return a.end(); }
    CIter end() const { return a.end(); }
    int size() const { return a.size(); }
    bool empty() const { return a.empty(); }
    Elem& back(){ return a.back(); }
    const Elem& back() const { return a.back(); }
    vec& sortuni(){ (*this)().sort(); a.erase((*this)().uni(), end()); return *this; }
    vec sortunied(){ vec x = *this; x.sortuni(); return x; }
    Iter operator()(int x){ return a.begin() + x; }
    CIter operator()(int x) const { return a.begin() + x; }
    View operator()(int l, int r){ return { (*this)(l), (*this)(r) }; }
    CView operator()(int l, int r) const { return { (*this)(l), (*this)(r) }; }
    View operator()(){ return (*this)(0,size()); }
    CView operator()() const { return (*this)(0,size()); }
    Elem& operator[](int x){ return a[x]; }
    const Elem& operator[](int x) const { return a[x]; }
    Base& operator*(){ return a; }
    const Base& operator*() const { return a; }
    vec& push(Elem args){
        a.push_back(std::move(args));
        return *this;
    }
    template<class... Args>
    vec& emp(Args &&... args){
        a.emplace_back(std::forward<Args>(args) ...);
        return *this;
    }
    template<class Range>
    vec& app(Range& x){ for(auto& v : x){ emp(v); } return *this; }
    Elem pop(){ Elem x = std::move(a.back()); a.pop_back(); return x; }
    void resize(int sz){ a.resize(sz); }
    void reserve(int sz){ a.reserve(sz); }
    bool operator==(const vec& r) const { return a == r.a; }
    bool operator!=(const vec& r) const { return a != r.a; }
    bool operator<(const vec& r) const { return a < r.a; }
    bool operator<=(const vec& r) const { return a <= r.a; }
    bool operator>(const vec& r) const { return a > r.a; }
    bool operator>=(const vec& r) const { return a >= r.a; }
    vec<vec<Elem>> pile(int n) const { return vec<vec<Elem>>(n, *this); }
    template<class F> vec& filter(F f){
        int p = 0;
        for(auto& x : a) if(f(x)) std::swap(a[p++],x);
        resize(p); return *this;
    }
    vec& operator+=(const vec& r){ return app(r); }
    vec operator+(const vec& r) const { vec x = *this; x += r; return x; }
    vec operator*(int t) const { vec res; while(t--){ res += *this; } return res; }
private: Base a;
};

template<class IStr, class U, class T>
IStr& operator>>(IStr& is, vec<std::pair<U,T>>& v){ for(auto& x:v){ is >> x.first >> x.second; } return is; }
template<class IStr, class T>
IStr& operator>>(IStr& is, vec<T>& v){ for(auto& x:v){ is >> x; } return is; }
template<class OStr, class T>
OStr& operator<<(OStr& os, const vec<T>& v){
    for(int i=0; i<v.size(); i++){
        if(i){ os << ' '; } os << v[i];
    } return os;
}
template<class OStr, class U, class T>
OStr& operator<<(OStr& os, const vec<std::pair<U,T>>& v){
    for(int i=0; i<v.size(); i++){
        if(i){ os << ' '; } os << '(' << v[i].first << ',' << v[i].second << ')';
    } return os;
}
#include <cassert>
#include <numeric>

// FROM ATCODER LIBRARY
namespace nachia {

namespace internal {

std::vector<int> sa_naive(const std::vector<int>& s) {
    int n = int(s.size());
    std::vector<int> sa(n);
    std::iota(sa.begin(), sa.end(), 0);
    std::sort(sa.begin(), sa.end(), [&](int l, int r) {
        if (l == r) return false;
        while (l < n && r < n) {
            if (s[l] != s[r]) return s[l] < s[r];
            l++;
            r++;
        }
        return l == n;
    });
    return sa;
}

std::vector<int> sa_doubling(const std::vector<int>& s) {
    int n = int(s.size());
    std::vector<int> sa(n), rnk = s, tmp(n);
    std::iota(sa.begin(), sa.end(), 0);
    for (int k = 1; k < n; k *= 2) {
        auto cmp = [&](int x, int y) {
            if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
            int rx = x + k < n ? rnk[x + k] : -1;
            int ry = y + k < n ? rnk[y + k] : -1;
            return rx < ry;
        };
        std::sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        }
        std::swap(tmp, rnk);
    }
    return sa;
}

std::vector<int> sa_is(const std::vector<int>& s, int upper) {
    int n = int(s.size());
    if (n == 0) return {};
    if (n == 1) return {0};
    if (n == 2) {
        if (s[0] < s[1]) {
            return {0, 1};
        } else {
            return {1, 0};
        }
    }
    if (n < 10) {
        return sa_naive(s);
    }
    if (n < 40) {
        return sa_doubling(s);
    }

    std::vector<int> sa(n);
    std::vector<bool> ls(n);
    for (int i = n - 2; i >= 0; i--) {
        ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
    }
    std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
    for (int i = 0; i < n; i++) {
        if (!ls[i]) {
            sum_s[s[i]]++;
        } else {
            sum_l[s[i] + 1]++;
        }
    }
    for (int i = 0; i <= upper; i++) {
        sum_s[i] += sum_l[i];
        if (i < upper) sum_l[i + 1] += sum_s[i];
    }

    auto induce = [&](const std::vector<int>& lms) {
        std::fill(sa.begin(), sa.end(), -1);
        std::vector<int> buf(upper + 1);
        std::copy(sum_s.begin(), sum_s.end(), buf.begin());
        for (auto d : lms) {
            if (d == n) continue;
            sa[buf[s[d]]++] = d;
        }
        std::copy(sum_l.begin(), sum_l.end(), buf.begin());
        sa[buf[s[n - 1]]++] = n - 1;
        for (int i = 0; i < n; i++) {
            int v = sa[i];
            if (v >= 1 && !ls[v - 1]) {
                sa[buf[s[v - 1]]++] = v - 1;
            }
        }
        std::copy(sum_l.begin(), sum_l.end(), buf.begin());
        for (int i = n - 1; i >= 0; i--) {
            int v = sa[i];
            if (v >= 1 && ls[v - 1]) {
                sa[--buf[s[v - 1] + 1]] = v - 1;
            }
        }
    };

    std::vector<int> lms_map(n + 1, -1);
    int m = 0;
    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms_map[i] = m++;
        }
    }
    std::vector<int> lms;
    lms.reserve(m);
    for (int i = 1; i < n; i++) {
        if (!ls[i - 1] && ls[i]) {
            lms.push_back(i);
        }
    }

    induce(lms);

    if (m) {
        std::vector<int> sorted_lms;
        sorted_lms.reserve(m);
        for (int v : sa) {
            if (lms_map[v] != -1) sorted_lms.push_back(v);
        }
        std::vector<int> rec_s(m);
        int rec_upper = 0;
        rec_s[lms_map[sorted_lms[0]]] = 0;
        for (int i = 1; i < m; i++) {
            int l = sorted_lms[i - 1], r = sorted_lms[i];
            int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
            int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
            bool same = true;
            if (end_l - l != end_r - r) {
                same = false;
            } else {
                while (l < end_l) {
                    if (s[l] != s[r]) {
                        break;
                    }
                    l++;
                    r++;
                }
                if (l == n || s[l] != s[r]) same = false;
            }
            if (!same) rec_upper++;
            rec_s[lms_map[sorted_lms[i]]] = rec_upper;
        }

        auto rec_sa =
            sa_is(rec_s, rec_upper);

        for (int i = 0; i < m; i++) {
            sorted_lms[i] = lms[rec_sa[i]];
        }
        induce(sorted_lms);
    }
    return sa;
}

}  // namespace internal

std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
    assert(0 <= upper);
    for (int d : s) {
        assert(0 <= d && d <= upper);
    }
    auto sa = internal::sa_is(s, upper);
    return sa;
}

template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
    int n = int(s.size());
    std::vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
    std::vector<int> s2(n);
    int now = 0;
    for (int i = 0; i < n; i++) {
        if (i && s[idx[i - 1]] != s[idx[i]]) now++;
        s2[idx[i]] = now;
    }
    return internal::sa_is(s2, now);
}

std::vector<int> suffix_array(const std::string& s) {
    int n = int(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) {
        s2[i] = s[i];
    }
    return internal::sa_is(s2, 255);
}

template <class T>
std::vector<int> lcp_array(const std::vector<T>& s,
                           const std::vector<int>& sa) {
    int n = int(s.size());
    assert(n >= 1);
    std::vector<int> rnk(n);
    for (int i = 0; i < n; i++) {
        rnk[sa[i]] = i;
    }
    std::vector<int> lcp(n - 1);
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (h > 0) h--;
        if (rnk[i] == 0) continue;
        int j = sa[rnk[i] - 1];
        for (; j + h < n && i + h < n; h++) {
            if (s[j + h] != s[i + h]) break;
        }
        lcp[rnk[i] - 1] = h;
    }
    return lcp;
}

std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
    int n = int(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) {
        s2[i] = s[i];
    }
    return lcp_array(s2, sa);
}

} // namespace nachia

namespace nachia{

template<
    class S,
    S op(S l, S r)
>
struct Segtree {
private:
    int N;
    std::vector<S> A;
    int xN;

    void mergev(int i){
        if(i < N) A[i] = op(A[i*2], A[i*2+1]);
    }

    template<class E>
    int minLeft2(int r, E cmp, int a = 0, int b = 0, int i = -1) const {
        static S x;
        if(i == -1){ a=0; b=N; i=1; x=A[0]; }
        if(r <= a) return a;
        if(b <= r){
            S nx = op(A[i], x);
            if(cmp(nx)){ x = nx; return a; }
        }
        if(b - a == 1) return b;
        int q = minLeft2(r, cmp, (a+b)/2, b, i*2+1);
        if(q > (a+b)/2) return q;
        return minLeft2(r, cmp, a, (a+b)/2, i*2);
    }
    
    template<class E>
    int maxRight2(int l, E cmp, int a = 0, int b = 0, int i = -1) const {
        static S x;
        if(i == -1){ a=0; b=N; i=1; x=A[0]; }
        if(b <= l) return b;
        if(l <= a){
            S nx = op(x, A[i]);
            if(cmp(nx)){ x = nx; return b; }
        }
        if(b - a == 1) return a;
        int q = maxRight2(l, cmp, a, (a+b)/2, i*2);
        if(q < (a+b)/2) return q;
        return maxRight2(l, cmp, (a+b)/2, b, i*2+1);
    }

public:
    Segtree() : N(0) {}
    Segtree(int n, S e) : xN(n) {
        N = 1; while (N < n) N *= 2;
        A.assign(N * 2, e);
    }
    Segtree(const std::vector<S>& a, S e) : Segtree(a.size(), e){
        for(int i=0; i<(int)a.size(); i++) A[i + N] = a[i];
        for(int i=N-1; i>=1; i--) mergev(i);
    }

    S getE() const { return A[0]; }

    void set(int p, S x){
        p += N; A[p] = x;
        for(int d=1; (1<<d)<=N; d++) mergev(p>>d);
    }

    S get(int p) const { return A[N+p]; }

    S prod(int l, int r) const {
        l += N; r += N;
        S ql = A[0], qr = A[0];
        while(l<r){
            if(l&1) ql = op(ql, A[l++]);
            if(r&1) qr = op(A[--r], qr);
            l /= 2;
            r /= 2;
        }
        return op(ql, qr);
    }

    S allProd() const { return A[1]; }

    // bool cmp(S)
    template<class E>
    int minLeft(int r, E cmp) const {
        return minLeft2(r, cmp);
    }

    // bool cmp(S)
    template<class E>
    int maxRight(int l, E cmp) const {
        int x = maxRight2(l, cmp);
        return x > xN ? xN : x;
    }
};

} // namespace nachia

namespace nachia {
    template<class T, class Cmp = std::less<T>>
    struct PointSetRangeMin{
    private:
        static T minop(T l, T r){ return std::min(l, r, Cmp()); }
        using Base = Segtree<T, minop>;
        Base base;
        Cmp cmpx;
    public:
        PointSetRangeMin() {}
        PointSetRangeMin(int len, T INF)
            : base(len, INF){}
        PointSetRangeMin(const std::vector<T>& init, T INF)
            : base(init, INF){}
        T min(int l, int r){ return base.prod(l, r); }
        T min(){ return base.allProd(); }
        void set(int pos, T val){ base.set(pos, val); }
        T getinf() const { return base.getE(); }
        void setinf(int pos){ set(pos, getinf()); }
        T get(int pos){ return base.get(pos); }
        void chmin(int pos, T val){ base.set(pos, minop(get(pos), val)); }
        int lBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return cmpx(val, x); }); }
        int uBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return !cmpx(x, val); }); }
        int lBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return cmpx(val, x); }); }
        int uBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return !cmpx(x, val); }); }
        template<class E>
        int minLeft(int r, E cmp){ return base.minLeft(r, cmp); }
        template<class E>
        int maxRight(int l, E cmp){ return base.maxRight(l, cmp); }
        int argmin(int l, int r){
            auto v = this->min(l, r);
            if(!cmpx(v, getinf())) return -1;
            return lBoundRight(l, v);
        }
    };
} // namespace nachia

namespace nachia{

template<class Elem>
std::vector<int> EnumeratePalindromes(const std::vector<Elem>& A, bool extend = false) {
    int n = int(A.size());
    if (n == 0) return { 0 };
    std::vector<int> res(n);
    int r = 0;
    for(int i=0; i<n; ){
        while (0<=i-r && i+r<n && A[i-r] == A[i+r]) r++;
        res[i] = r;
        int di = 1;
        while ((0<=i-di && i+di<n) && res[i-di] < r-di) {
            res[i+di] = res[i-di];
            di++;
        }
        r -= di;
        i += di;
    }
    return res;
}

} // namespace nachia

namespace nachia{

int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x8888'8888;
    constexpr u64 mi = 0x1111'1111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333'3333'2222'1100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}


namespace nachia{

struct WaveletMatrix{
    using u64 = unsigned long long;
    struct WordBlock{ u64 table; int ptr; };
    int n;
    int S;
    int logS;
    std::vector<std::vector<WordBlock>> Table;

    WaveletMatrix() {}
  
    WaveletMatrix(int maxVal, std::vector<int> A){
        S = 1; logS = 0;
        n = A.size();
        while(S <= maxVal){ S *= 2; logS += 1; }
        Table.resize(logS);
        for(int d=logS-1; d>=0; d--){
            std::vector<WordBlock> tableBuf(n/64+2,{0,0});
            for(int i=0; i<n; i++) tableBuf[i/64].table |= (u64)((A[i]>>d) & 1) << (i%64);
            for(int i=1; i<=n/64+1; i++) tableBuf[i].ptr = tableBuf[i-1].ptr + Popcount(tableBuf[i-1].table);
            std::vector<int> buf;
            for(int b : {0,1<<d}) for(int a : A) if((a&(1<<d))==b) buf.push_back(a);
            std::swap(Table[d],tableBuf);
            std::swap(A,buf);
        }
    }
    int getLevelRank(int level, int p) const {
        int res = Table[level][p/64].ptr + Popcount(Table[level][p/64].table & ~(~(u64)0 << (p%64)));
        return res;
    }
    int getLeftPointer(int level, int p) const {
        return p - getLevelRank(level,p);
    }
    int getRightPointer(int level, int p) const {
        return n - Table[level].back().ptr + getLevelRank(level,p);
    }
    int get(int p) const {
        int res = 0;
        for(int d=logS-1; d>=0; d--){
            res *= 2;
            if(Table[d][p/64].table & ((u64)1 << (p%64))){
                res |= 1;
                p = getRightPointer(d,p);
            }
            else{
                p = getLeftPointer(d,p);
            }
        }
        return res;
    }
    int count(int l, int r, int val) const {
        for(int d=logS-1; d>=0; d--){
            if(val & (1<<d)){
                l = getRightPointer(d,l);
                r = getRightPointer(d,r);
            }
            else{
                l = getLeftPointer(d,l);
                r = getLeftPointer(d,r);
            }
        }
        return r - l;
    }
    int countRange(int l, int r, int rval) const {
        if(rval == 0) return 0;
        int ans = 0;
        for(int d=logS-1; d>=0; d--){
            if(rval & (1<<d)){
                ans += getLeftPointer(d,r) - getLeftPointer(d,l);
                l = getRightPointer(d,l);
                r = getRightPointer(d,r);
            } else{
                l = getLeftPointer(d,l);
                r = getLeftPointer(d,r);
            }
        }
        return ans;
    }
    int count(int l, int r, int lval, int rval) const {
        return countRange(l, r, rval) - countRange(l, r, lval);
    }
    int getKthSmallest(int l, int r, int k) const {
        int res = 0;
        for(int d=logS-1; d>=0; d--){
            res *= 2;
            int zerocnt = r - l;
            zerocnt -= getLevelRank(d,r);
            zerocnt += getLevelRank(d,l);
            if(k < zerocnt){
                l = getLeftPointer(d,l);
                r = getLeftPointer(d,r);
            }
            else{
                res += 1;
                k -= zerocnt;
                l = getRightPointer(d,l);
                r = getRightPointer(d,r);
            }
        }
        return res;
    }
    int getMaxNoGreaterThanRec(int l, int r, int k, int d) const {
        if(l >= r) return -1;
        if(d < 0) return 0;
        if(!(k & (1 << d))){
            return getMaxNoGreaterThanRec(getLeftPointer(d,l), getLeftPointer(d,r), k, d-1);
        } else {
            int q = getMaxNoGreaterThanRec(getRightPointer(d,l), getRightPointer(d,r), k-(1<<d), d-1);
            if(q != -1) return q + (1 << d);
            return getMaxNoGreaterThanRec(getLeftPointer(d,l), getLeftPointer(d,r), (1<<d)-1, d-1);
        }
    }
    int getMaxNoGreaterThan(int l, int r, int k) const {
        return getMaxNoGreaterThanRec(l, r, k, logS-1);
    }
};

}

void testcase(){
    string S; cin >> S;
    int N = S.size();
    vector<int> Si(N*2-1, -1);
    rep(i,N) Si[i*2] = S[i] - 'a';
    auto pals = nachia::EnumeratePalindromes(Si);
    string SrS = S + "$#" + string(S.rbegin(), S.rend());
    //cout << SrS << endl;
    auto sa = nachia::suffix_array(SrS);
    auto lcp = nachia::lcp_array(SrS, sa);
    auto rmq = nachia::PointSetRangeMin<int>(lcp, 1001001001);
    auto wm = nachia::WaveletMatrix(N*2+1, sa);
    //for(int sai : sa) cout << SrS.substr(sai) << endl;
    vector<int> isa(sa.size());
    rep(i,sa.size()) isa[sa[i]] = i;
    vector<int> D(N);
    rep(i,N-1) D[i+1] = (S[i] == S[i+1] ? 0 : 1);
    rep(i,N-1) D[i+1] += D[i];
    int ansLowerBound = 0;
    auto equalRange = [&](int l, int r) -> int {
        if(D[r-1] == D[l]) return 0;
        int ng = 0;
        int ok = (r-l)/2;
        while(ng + 1 < ok){
            int w = (ng + ok) / 2;
            (D[r-w-1] == D[l+w] ? ok : ng) = w;
        }
        return ok;
    };
    rep(m,pals.size()){
        int l = (m + 1 - pals[m]) / 2;
        int r = (m + 1 + pals[m]) / 2;
        int k = equalRange(l, r);
        chmax(ansLowerBound, (r-l-1) - k);
        //cout << "m = " << m << " , l = " << l << " , r = " << r << " , k = " << k << endl;
    }
    auto simulate = [&](int l, int r) -> int {
        int ans = 0;
        //cout << "check l = " << l << " , r = " << r << endl;
        while(true){
            if(N-r <= (r-l)) break;
            int f = isa[l];
            int fl = rmq.uBoundLeft(f, r-l);
            int fr = rmq.uBoundRight(f, r-l) + 1;
            //cout << "fl = " << fl << " , fr = " << fr << endl;
            int x = wm.getMaxNoGreaterThan(fl, fr, 2*N+2-r-(r-l)-1);
            //cout << "2*N+2-r-1-(r-l) = " << 2*N+2-r-1-(r-l) << endl;
            if(x < N+2) break;
            ans += 1;
            r = 2*N+2 - x;
            //cout << "l = " << l << " , r = " << r << " , x = " << x << endl;
        }
        return ans;
    };
    rep(m,pals.size()){
        int l = (m + 1 - pals[m]) / 2;
        int r = (m + 1 + pals[m]) / 2;
        while(true){
            if(l >= r) break;
            int k = equalRange(l, r);
            int minAns = (r-l-1) - k;
            if(minAns + 20 < ansLowerBound) break;
            int thisans = minAns + simulate(l, r);
            chmax(ansLowerBound, thisans);
            l += 1; r -= 1;
        }
    } 
    cout << ansLowerBound << endl;
    //cout << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    rep(t,T) testcase();
    return 0;
}