//author: Negationist (Jacob Ezieme)
//date: 5/31/2025
//description: data structure with the ability to store, piecewise, linear, convex functions
//status: moderately tested, all functions were used in an accepted submission to "G - Travelling Salesman Problem" in AtCoder Beginner Contest 406, link: "https://atcoder.jp/contests/abc406/tasks/abc406_g"

template <typename T>
struct BoundedSegtree {
    ll L, R, n;
    std::vector<T> tree;
    std::function<T(T, T)> merge; //merge function, you need to provide it
    T identity;
    BoundedSegtree(std::function<T(T, T)> merge_op, T id, ll left, ll right)
        : L(left), R(right), n(right - left + 1), merge(merge_op), identity(id) {
            assert(L <= R);
            tree.assign(4 << std::__lg(n), identity);
        }
    ll idx(ll x) const { return x - L; }
    void set(ll x, T v) {
        assert(L <= x && x <= R);
        set(1, 0, n - 1, idx(x), v);
    }
    void add(ll x, T delta) {
        assert(L <= x && x <= R);
        add(1, 0, n - 1, idx(x), delta);
    }
    T query(ll ql, ll qr) const {
        if (qr < ql) return identity;
        return query(1, 0, n - 1, idx(ql), idx(qr));
    }
    void build(const std::vector<T>& data) {
        assert((ll)data.size() <= n);
        build(1, 0, n - 1, data);
    }
    void set(ll p, ll l, ll r, ll i, T v) {
        if (l == r) {
            tree[p] = v;
            return;
        }
        ll m = (l + r) >> 1;
        if (i <= m) {
            set(p << 1, l, m, i, v);
        } else {
            set(p << 1 | 1, m + 1, r, i, v);
        }
        tree[p] = merge(tree[p << 1], tree[p << 1 | 1]);
    }
    void add(ll p, ll l, ll r, ll i, T delta) {
        if (l == r) {
            tree[p] = merge(tree[p], delta);
            return;
        }
        ll m = (l + r) >> 1;
        if (i <= m) {
            add(p << 1, l, m, i, delta);
        } else {
            add(p << 1 | 1, m + 1, r, i, delta);
        }
        tree[p] = merge(tree[p << 1], tree[p << 1 | 1]);
    }
    T query(ll p, ll l, ll r, ll ql, ll qr) const {
        if (qr < l || r < ql) return identity;
        if (ql <= l && r <= qr) return tree[p];
        ll m = (l + r) >> 1;
        return merge(
            query(p << 1,     l,    m,    ql, qr),
            query(p << 1 | 1, m + 1, r,    ql, qr)
        );
    }
    void build(ll p, ll l, ll r, const std::vector<T>& data) {
        if (l == r) {
            tree[p] = (l < (ll)data.size() ? data[l] : identity);
            return;
        }
        ll m = (l + r) >> 1;
        build(p << 1,     l,    m,     data);
        build(p << 1 | 1, m + 1, r,     data);
        tree[p] = merge(tree[p << 1], tree[p << 1 | 1]);
    }
};

struct slope_trick { //please look at the implementation, do not take the complexities at face value, they are often worse than average case
    using Seg = BoundedSegtree<ll>;
    ll m = 0, b = 0; //slope and y intercept of the right side function
    ll L = 0, R = 0; //leftmost and rightmost points that could have a change in slope
    std::map<ll, ll> points; //slope delta at each point in [L,R]
    bool use_history = false; //if true, you will log all your changes into the "changes" vector
    bool use_tree = false; //if true, you can find the slope at any point in O(logn)
    bool found = false; //if the last query found something valid, this is true, else it is false, see the query function for more details
    std::vector<std::tuple<ll, ll, ll>> changes; //holds the changes, format is {type,y,z}, see the implementation in the rollback function to understand better
    std::unique_ptr<Seg> tree; //segment tree for point slope queries

    slope_trick(bool enable_history = false, //default parameters, since you could quickly mle if you are not careful, by default, history and segment tree queries are turned off
                bool enable_tree    = false,
                ll   m_init         = 0,
                ll   b_init         = 0,
                ll   left_bound     = -1,
                ll   right_bound    = 1)
        : m(m_init), b(b_init), L(left_bound), R(right_bound),
          use_history(enable_history), use_tree(enable_tree)
    {
        if (use_tree) {
            tree = std::make_unique<Seg>(op, 0LL, L, R);
        }
    }

    void log_change(ll type, ll x, ll d) { //logs changes that can be reversed later
        if (use_history) changes.emplace_back(type, x, d);
    }

    ll timestamp() { //returns the size of the changes vector, which is useful for rolling back the function to a specific point, see the rollback function
        return (ll)changes.size();
    }

    ll slope_at(ll x) { //slope at point x,  NOTE THAT at turning points the LOWER slope is considered. Be careful, using this function without a tree is slow
        if (!use_tree){ //O(|points|)
            ll cur = m;
            auto it = points.rbegin();
            while(it!=points.rend() && it->ff >= x){
                cur-=(it->ss);
                ++it;
            }
            return cur;
        } else{
            if (x > R) { //O(log(R-L))
                return m;
            } else if (L <= x && x <= R) {
                return m - tree->query(x, R);
            } else {
                return m - tree->query(L, R);
            }
        }
    }

    void rollback(ll idx) { //rolls the tree back to the last time when the the number of changes was idx, if it possible, O(|changes|*log(max(R-L, |points|))
        while ((ll)changes.size() > idx) {
            auto [type, x, d] = changes.back();
            changes.pop_back();
            if (type == 1) {
                m -= x;
            } else if (type == 2) {
                b -= x;
            } else {
                points[x] -= d;
                if (!points[x]) points.erase(x);
                if (use_tree) {
                    tree->set(x, points.count(x) ? points[x] : 0); //add
                }
            }
        }
    }

    void add_slope(ll x, ll delta) { //add slope delta to a point, and logs the change if logs are activated, O(log(max(R-L, |points|))
        if (!delta) return;
        points[x] += delta;
        if (!points[x]) points.erase(x);
        if (use_tree) {
            tree->set(x, points.count(x) ? points[x] : 0);
        }
        if (use_history) {
            log_change(3, x, delta);
        }
    }

    bool set_max(ll mx) { //sets the maximum slope of the function to mx, returns true if successful, else it returns false, O(|points|*log(max(R-L, |points|)), often there is some global bound on the complexity this function adds, you can only remove things as many times as you add them
        ll old_m = m, old_b = b;
        auto it = points.rbegin();
        std::vector<std::pair<ll, ll>> operations;
        while (m > mx && it != points.rend()) {
            ll x   = it->first;
            ll cnt = it->second;
            ++it;
            ll y    = m * x + b;
            ll take = std::min(cnt, m - mx);
            operations.push_back({ x, -take });
            m -= take;
            b = y - m * x;
        }
        for (auto [x, y] : operations) {
            add_slope(x, y);
        }
        log_change(1, m - old_m, 0);
        log_change(2, b - old_b, 0);
        return (m <= mx);
    }

    // NOTE THAT there is no maximum in a convex function unless it is flat, note that in a problem with concave functions, you can simply mirror the functions about the x axis
    std::pair<ll, ll> get_min() { //returns the right most point where the function is minimum or {0,b} where there is no slope delta
        ll min_slope = slope_at(L);
        if (min_slope > 0 || m < 0) {
            return std::make_pair(-1LL, -1LL);
        }
        if (!points.size()) {
            return std::make_pair(0LL, b);
        }
        auto it = points.rbegin();
        ll cur = m;
        ll x   = it->first;
        ll y   = m * x + b;
        while (cur > 0 && it != points.rend()) {
            y = y + cur * ((it->first) - x);
            x = it->first;
            cur -= it->second;
            ++it;
        }
        return std::make_pair(x, y);
    }

    bool set_min(ll mn) { //sets the minimum slope of the function to mn, returns true if successful, else it returns false, O(|points|*log(max(R-L, |points|)), often there is some global bound on the complexity this function adds, you can only remove things as many times as you add them
        if (m < mn) return false;
        if (use_tree) {
            ll delta_old = m - slope_at(L);
            ll delta_new = m - mn;
            ll pool      = delta_old - delta_new;
            std::vector<std::pair<ll, ll>> operations;
            for (auto it = points.begin(); it != points.end() && pool > 0;) {
                ll x   = it->first;
                ll cnt = it->second;
                ++it;
                ll take = std::min(cnt, pool);
                operations.push_back({ x, -take });
                pool -= take;
            }
            for (auto [x, y] : operations) {
                add_slope(x, y);
            }
        } else {
            ll cur = m;
            std::vector<std::pair<ll, ll>> operations;
            for (auto it = points.rbegin(); it != points.rend();) {
                ll x   = it->first;
                ll cnt = it->second;
                ++it;
                ll take = std::max(cnt - (cur - mn), 0LL);
                operations.push_back({ x, -take });
                cur -= (points[x] - take);
            }
            for (auto [x, y] : operations) {
                add_slope(x, y);
            }
        }
        return true;
    }

    ll query_right(ll x) { // find the rightmost point such that the slope is <= x, note that at a turning point, if the slope on the left is acceptable, it will be accepted, with tree: O(log(L-R)*log(L-R)), without tree: O(log(L-R)*|points|)
        ll lo = L, hi = R;
        found = false;
        while (lo <= hi) {
            ll mid = lo + (hi - lo) / 2;
            if (slope_at(mid) <= x) {
                found = true;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return hi;
    }

    ll query_left(ll x) { // find the leftmost point such that the slope is >= x, note that at a turning point, if the slope on the right is acceptable, it will be accepted, with tree: O(log(L-R)*log(L-R)), without tree: O(log(L-R)*|points|)
        ll lo = L, hi = R;
        found = false;
        while (lo <= hi) {
            ll mid = lo + (hi - lo) / 2;
            if (slope_at(mid) + (points.count(mid) ? points[mid] : 0) >= x) {
                found = true;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    slope_trick& operator+=(const slope_trick& o) {
        m += o.m;
        b += o.b;
        log_change(1, o.m, 0);
        log_change(2, o.b, 0);
        for (auto [x, d] : o.points) {
            add_slope(x, d);
        }
        return *this;
    }

    slope_trick operator+(const slope_trick& o) const {
        slope_trick res(
            use_history || o.use_history,
            use_tree    || o.use_tree,
            m + o.m,
            b + o.b,
            std::min(L, o.L),
            std::max(R, o.R)
        );
        for (auto [x, d] : points) {
            res.add_slope(x, d);
        }
        for (auto [x, d] : o.points) {
            res.add_slope(x, d);
        }
        return res;
    }

    static slope_trick abs_func(ll slope, ll c) { //return the function representing slope|x-c|
        slope_trick s(
            false,
            false,
            slope,
            -c * slope,
            c - 1,
            c + 1
        );
        s.points[c] = 2 * slope;
        return s;
    }
};

#include <bits/stdc++.h>
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define print(x) cout << (x) << endln
#define each(a, x) for(auto &&a : x)

using namespace std;

void solve(){
    int n;
    cin >> n;
    vii points(n);
    for(int i=0;i<n;i++){
        cin >> points[i].ff >> points[i].ss;
    }
    sort(points.begin(),points.end());
    vi x(n),y(n);
    for(int i=0;i<n;i++){
        x[i] = points[i].ff;
        y[i] = points[i].ss;
    }
    int ans = 0;
    pii d = {0,0};
    multiset<int> left,right;
    int l = 1, r= n/4;
    while(l<=r){
        int mid = l+(r-l)/2;
        bool found = false;
        right.clear();
        left.clear();
        for(int i=0;i<n;i++){
            right.insert(y[i]);
        }
        for(int i=0;i<n;i++){
            left.insert(y[i]);
            right.erase(right.find(y[i]));
            while(i+1<n && x[i+1]==x[i]){
                left.insert(y[i+1]);
                right.erase(right.find(y[i+1]));
                i++;
            }
            if(left.size()<2*mid || right.size()<2*mid) continue;
            int u1,d1,u2,d2;
            int lo = *(left.begin()), hi = *(--left.end());
            while(lo<=hi){
                int _mid = lo+(hi-lo)/2;
                auto prev = left.lower_bound(_mid);
                int num = distance(left.begin(),prev)+1;
                if(num>=mid && left.size()-num>=mid){
                    prev++;
                    d1 = *prev;
                    hi = _mid-1;
                } else{
                    lo = _mid+1;
                }
            }
            lo = *(left.begin()); hi = *(--left.end());
            while(lo<=hi){
                int _mid = lo+(hi-lo)/2;
                auto prev = left.upper_bound(_mid);
                int num = distance(prev,left.end());
                if(num>=mid && left.size()-num>=mid){
                    lo = _mid+1;
                    u1 = *prev;
                } else{
                    hi = _mid-1;
                }
            }
            lo = *(right.begin()), hi = *(--right.end());
            while(lo<=hi){
                int _mid = lo+(hi-lo)/2;
                auto prev = right.lower_bound(_mid);
                int num = distance(right.begin(),prev)+1;
                if(num>=mid && right.size()-num>=mid){
                    prev++;
                    d2 = *prev;
                    hi = _mid-1;
                } else{
                    lo = _mid+1;
                }
            }
            lo = *(right.begin()); hi = *(--right.end());
            while(lo<=hi){
                int _mid = lo+(hi-lo)/2;
                auto prev = right.lower_bound(_mid);
                int num = distance(prev,right.end());
                if(num>=mid){
                    if(right.size()-num>=mid){
                        u2 = *prev;
                    }
                    lo = _mid+1;
                } else{
                    hi = _mid-1;
                }
            }
            int top = min(u1,u2), bottom = max(d1,d2);
            if(top>=bottom){
                found = true;
                if(mid>ans){
                    ans = mid;
                    d = {x[i]+1,top};
                }
                break;
            }
        }
        if(found){
            l = mid+1;
        } else{
            r = mid-1;
        }
    }
    cout << ans << "\n" << d.ff << " " << d.ss << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

int vote(char x, char y, char z){
    int res = 0;
    res+=(x=='A'?1:0);
    res+=(y=='A'?1:0);
    res+=(z=='A'?1:0);
    return (res>1);
}

void solve(){
    int n;
    cin >> n;
    string s[2];
    for(int i=0;i<2;i++){
        cin >> s[i];
        s[i] = "+"+s[i];
    }
    vector<vector<int>> dp(n+10,vector<int>(3,-1));
    dp[0][0] = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            if(dp[i][j]==-1) continue;
            if(j==0){
                dp[i+3][0] = max(dp[i+3][0], dp[i][0] + vote(s[0][i+1],s[0][i+2],s[0][i+3]) + vote(s[1][i+1],s[1][i+2],s[1][i+3]));
                dp[i+1][1] = max(dp[i+1][1], dp[i][0] + vote(s[0][i+1],s[1][i+1],s[0][i+2]));
                dp[i+1][2] = max(dp[i+1][2], dp[i][0] + vote(s[0][i+1],s[1][i+1],s[1][i+2]));
            } else if(j==1){
                dp[i+3][1] = max(dp[i+3][1], dp[i][1]+vote(s[0][i+2],s[0][i+3],s[0][i+4])+vote(s[1][i+1],s[1][i+2],s[1][i+3]));
                dp[i+2][0] = max(dp[i+1][0], dp[i][1]+vote(s[1][i+1], s[1][i+2], s[0][i+2]));
            } else{
                dp[i+3][2] = max(dp[i+3][2], dp[i][2]+vote(s[0][i+1],s[0][i+2],s[0][i+3])+vote(s[1][i+2],s[1][i+3],s[1][i+4]));
                dp[i+2][0] = max(dp[i+2][0], dp[i][2]+vote(s[0][i+1], s[0][i+2], s[1][i+2]));
            }
        }
    }
    cout << dp[n][0] << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

void solve(){
    int n,k;
    cin >> n >> k;
    vi a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    if(k >= 3){
        cout << "0\n";
        return;
    }
    sort(a.begin(), a.end());
    if(k==2){
        int mn = a[0];
        for(int i=0;i<n-2;i++){
            for(int j=1; j+i <n; j++){
                int diff = a[i+j]-a[i];
                int l=0, r=n-1;
                while(l<=r){
                    int mid = l +(r-l)/2;
                    if(a[mid]<=diff){
                        l = mid+1;
                    } else{
                        r = mid-1;
                    }
                }
                if(r>=0) {
                    mn = min(mn, diff-a[r]);
                }
                if(r+1<n) {
                    mn = min(mn, a[r+1] - diff);
                }
                mn = min(mn, diff);
            }
        }
        cout << mn << "\n";

    }
    if(k==1){
        int mn = a[0];
        for(int i=0;i<n-1;i++){
            mn = min(mn, a[i+1]-a[i]);
        }
        cout << mn << "\n";
        return;
    }

}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

int A;
int B = ((1LL<<61) - 1);

using namespace std;

void computehash(string &s, vi &h){
    int n = s.size();
    h[0] = s[0];
    for(int i=1;i<n;i++){
        h[i] = (h[i-1]*A + s[i])%B;
    }
}

void solve(){
    string s;
    cin >> s;
    int n = s.size();
    vi h(n);
    computehash(s, h);
    vi pow(n);
    pow[0] = 1;
    for(int i=1;i<n;i++){
        pow[i] = (pow[i-1]*A)%B;
    }
    for(int l=n-1;l>1;l--){
        int a = l-1;
        int b = n-l;
        if(a<b) break;
        cout << "\n";
        int hash1 = h[a];
        int hash2 = (h[n-1] - h[b-1]*pow[n-b])%B;
        if(hash1 ==  hash2){
            cout << "YES\n";
            cout << s.substr(1,l);
            return;
        }
    }
    cout << "NO\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> dist(1,B-1);
    A = dist(rng);
    solve();
    return 0;
}

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

void solve(){
    int n,k,m;
    string s;
    cin >> n >> k >> m >> s;
    string out;
    int cnt[k] = {};
    int total = 0;
    for(int i=0;i<m;i++){
        bool good = true;
        if(s[i] < 'a'+k){
            cnt[s[i]-'a']++;
        }
        for(int j=0;j<k;j++){
            if(cnt[j]<1){
                good = false;
                break;
            }
        }
        if(!good) continue;
        out.pb(s[i]);
        for(int j=0;j<k;j++){
            cnt[j] = 0;
        }
        total++;
    }
    if(total>=n){
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
    cout << out;
    for(int i=0;i<k;i++){
        if(cnt[i]==0){
            for(int j=0;j<n-out.size();j++){
                cout << (char)('a'+i);
                cout << "\n";
                return;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
#define int unsigned long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

int mysqrt(int x) {
    int l = 0, r = x, ans = 0;
    while (l <= r) {
        int mid = l + (r-l)/2;
        if ((__uint128_t)mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

void solve(){
    int k;
    cin >> k;
    unsigned long long l=0,r=ULLONG_MAX;
    while(l<=r){
        int mid = l+(r-l)/2;
        int take = mysqrt(mid);
        int num = mid-take;
        if(num < k){
           l = mid+1;
        } else{
            r = mid - 1;
        }
    }
    cout << r+1 << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
#define int unsigned long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

int mysqrt(int x) {
    int l = 0, r = x, ans = 0;
    while (l <= r) {
        int mid = l + (r-l)/2;
        if ((__uint128_t)mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

void solve(){
    int k;
    cin >> k;
    unsigned long long l=0,r=ULLONG_MAX;
    while(l<=r){
        int mid = l+(r-l)/2;
        int take = mysqrt(mid);
        int num = mid-take;
        if(num < k){
           l = mid+1;
        } else{
            r = mid - 1;
        }
    }
    cout << r+1 << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int T,n,a[200005],mn[200005],mx[200005],l,r;
void solve(){
	cin>>n;
	for(int i=0;i<=n;i++)mn[i]=n+1,mx[i]=0;
	for(int i=1;i<=n;i++)cin>>a[i],mn[a[i]]=min(mn[a[i]],i),mx[a[i]]=max(mx[a[i]],i);
	for(int i=1;i<=n;i++){
		mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]);
		if(mx[i]-mn[i]>=i){cout<<"0\n";return;}
	}
	l=1,r=n;
	for(int i=1;i<=n;i++)l=max(l,i-a[i]+1),r=min(r,i+a[i]-1);
	cout<<r-l+1<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)solve();
	return 0;
}