#include<bits/stdc++.h>

using namespace std;

int n,m,ans;

char s[];

void doit(int l,int r)

{

    int d=,nw=;

    for(;l<r;l++,r--)

    {

        while(l+d<r-d&&nw+abs(s[l+d]-s[r-d])<=m)nw+=abs(s[l+d]-s[r-d]),d++;

        ans=max(ans,d);

        nw-=abs(s[l]-s[r]);

        d--;

    }

}

void sol()

{

    scanf("%d%s",&m,s);

    n=strlen(s);

    ans=;

    for(int i=n-;i>=;i--)doit(,i);

    for(int i=;i<n-;i++)doit(i,n-);

    printf("%d\n",ans);

}

int main()

{

    int tt;scanf("%d",&tt);

    while(tt--)sol();

    return ;

}

#include<bits/stdc++.h>

using namespace std;

int n,cc,cs,cnt[],vis[],c[],sz[];

long long ans,res;

vector<int>g[];

void dfs(int x,int p)

{

    sz[x]=;

    int ss=;

    for(int i=;i<g[x].size();i++)if(g[x][i]!=p)

    {

        int lst=cnt[c[x]];

        dfs(g[x][i],x);

        sz[x]+=sz[g[x][i]];

        int nw=cnt[c[x]]-lst;

        ss+=nw;

        nw=sz[g[x][i]]-nw;

        res+=1ll*nw*(nw-)/;

    }

    cnt[c[x]]+=sz[x]-ss;

}

void sol()

{

    cc=;

    memset(vis,,sizeof(vis));

    memset(cnt,,sizeof(cnt));

    for(int i=;i<=n;i++)scanf("%d",&c[i]),vis[c[i]]=;

    for(int i=;i<=n;i++)if(vis[i])cc++;

    for(int i=;i<=n;i++)g[i].clear();

    for(int i=;i<n;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}

    res=;

    dfs(,);

    ans=1ll*n*(n-)/*cc;

    for(int i=;i<=n;i++)if(vis[i])

    {

        int sz=n-cnt[i];

        res+=1ll*sz*(sz-)/;

    }

    ans-=res;

    printf("Case #%d: %lld\n",++cs,ans);

}

int main()

{

    while(scanf("%d",&n)==)sol();

    return ;

}

#include<bits/stdc++.h>

using namespace std;

long long k,a,b,c,dd,d[][];

vector<pair<long long,int> >g[];

void sol()

{

    scanf("%lld%lld%lld%lld%lld",&k,&a,&b,&c,&dd);

    long long w=*min(a,b);

    for(int i=;i<=;i++)g[i].clear();

    g[].push_back(make_pair(,a));

    g[].push_back(make_pair(,a));

    g[].push_back(make_pair(,b));

    g[].push_back(make_pair(,b));

    g[].push_back(make_pair(,c));

    g[].push_back(make_pair(,c));

    g[].push_back(make_pair(,dd));

    g[].push_back(make_pair(,dd));

    memset(d,0x3f,sizeof(d));

    d[][]=;

    queue<pair<int,int> >q;

    q.push(make_pair(,));

    while(!q.empty())

    {

        long long l=q.front().first,x=q.front().second;

        q.pop();

        for(int i=;i<;i++)if(d[g[x][i].first][(l+g[x][i].second)%w]>l+g[x][i].second)

        {

            d[g[x][i].first][(l+g[x][i].second)%w]=l+g[x][i].second;

            q.push(make_pair(l+g[x][i].second,g[x][i].first));

        }

    }

    long long ans=2e18;

    for(int i=;i<w;i++)if(d[][i]>k)ans=min(ans,d[][i]);else ans=min(ans,d[][i]+(k-d[][i]+w-)/w*w);

    printf("%lld\n",ans);

}

int main()

{

    int tt;cin>>tt;

    while(tt--)sol();

    return ;

}

#include<bits/stdc++.h>

using namespace std;

const int md=;

int n,vis[];

vector<pair<int,int> >g[];

vector<int>e,t;

void sol()

{

    scanf("%d",&n);

    for(int i=;i<=n*;i++)vis[i]=,g[i].clear();

    for(int i=;i<=n;i++)

    {

        int u,wu,v,wv;

        scanf("%d%d%d%d",&u,&wu,&v,&wv);

        g[i].push_back(make_pair(n+u,wu));

        g[n+u].push_back(make_pair(i,wu));

        g[i].push_back(make_pair(n+v,wv));

        g[n+v].push_back(make_pair(i,wv));

    }

    bool f=false;

    for(int i=;i<=n;i++)if(!g[n+i].size())f=true;

    if(f){printf("0\n");return;}

    int ans=;

    for(int i=n+;i<=*n;i++)if(g[i].size()==&&!vis[i])

    {

        int res=g[i][].second,lst=i,nw=g[i][].first;

        while(true)

        {

            vis[lst]=;vis[nw]=;

            int nxt=g[nw][].first+g[nw][].first-lst;

            if(g[nxt].size()==)res=;

            if(g[nxt].size()!=)

            {

                int j;

                for(j=;j<g[nxt].size();j++)if(g[nxt][j].first==nw)break;

                g[nxt].erase(g[nxt].begin()+j);

                break;

            }

            lst=nxt;

            nw=g[nxt][].first+g[nxt][].first-nw;

            int cc=(g[lst][].first==nw)?g[lst][].second:g[lst][].second;

            res=1ll*res*cc%md;

        }

        ans=1ll*ans*res%md;

    }

    for(int i=;i<=*n;i++)if(g[i].size()==&&!vis[i])

    {

        e.clear();t.clear();

        e.push_back(i);e.push_back(g[i][].first);

        t.push_back(g[i][].second);

        int lst=i,nw=g[i][].first;

        vis[lst]=;

        while(true)

        {

            vis[nw]=;

            int nxt=g[nw][].first+g[nw][].first-lst;

            int cc=(g[nw][].first==nxt)?g[nw][].second:g[nw][].second;

            t.push_back(cc);

            if(vis[nxt])break;

            lst=nw;nw=nxt;e.push_back(nw);

        }

        int res1=,res2=;

        for(int i=;i<t.size();i+=)res1=1ll*res1*t[i]%md;

        for(int i=;i<t.size();i+=)res2=1ll*res2*t[i]%md;

        res1=(res1+res2)%md;

        ans=1ll*ans*res1%md;

    }

    printf("%d\n",ans);

}

int main()

{

    int tt;scanf("%d",&tt);

    while(tt--)sol();

    return ;

}

#include<bits/stdc++.h>

using namespace std;

const double eps=1e-;

struct st{double mn,tg;}seg[];

int n,a[],ps[];

void up(int x){seg[x].mn=min(seg[x<<].mn,seg[x<<|].mn);}

void down(int x)

{

    seg[x<<].mn+=seg[x].tg;

    seg[x<<].tg+=seg[x].tg;

    seg[x<<|].mn+=seg[x].tg;

    seg[x<<|].tg+=seg[x].tg;

    seg[x].tg=;

}

void build(int x,int l,int r)

{

    seg[x]=(st){,};

    if(l==r)return;

    int md=l+r>>;build(x<<,l,md);build(x<<|,md+,r);

}

void modify(int x,int l,int r,int tl,int tr,double v)

{

    if(tl<=l&&r<=tr){seg[x].mn+=v,seg[x].tg+=v;return;}

    if(seg[x].tg)down(x);

    int md=l+r>>;

    if(tl<=md)modify(x<<,l,md,tl,tr,v);

    if(tr>md)modify(x<<|,md+,r,tl,tr,v);

    up(x);

}

double query(int x,int l,int r,int tl,int tr)

{

    if(tl<=l&&r<=tr)return seg[x].mn;

    if(seg[x].tg)down(x);

    int md=l+r>>;double ans=1e9;

    if(tl<=md)ans=min(ans,query(x<<,l,md,tl,tr));

    if(tr>md)ans=min(ans,query(x<<|,md+,r,tl,tr));

    return ans;

}

bool chk(double x)

{

    build(,,n);

    memset(ps,,sizeof(ps));

    for(int i=;i<=n;i++)

    {

        modify(,,n,ps[a[i]]+,i,);

        modify(,,n,,i,-x);

        if(query(,,n,,i)<=)return true;

        ps[a[i]]=i;

    }

    return false;

}

int main()

{

    int tt;scanf("%d",&tt);

    while(tt--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++)scanf("%d",&a[i]);

        double l=,r=,ans=;

        while(r-l>=eps)

        {

            double md=(l+r)/2.0;

            if(chk(md))ans=md,r=md;else l=md;

        }

        printf("%.6f\n",ans);

    }

    return ;

}

#include<bits/stdc++.h>

using namespace std;

const long long md=998244353ll;

int n,m,a[],b[];

long long dp[][];

void sol()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<n;i++)scanf("%d",&a[i]);

    for(int i=;i<m;i++)scanf("%d",&b[i]);

    long long ans=;

    memset(dp,,sizeof(dp));

    for(int i=;i<n;i++)

    {

        long long s1=,s2=;//·å£¬¹È

        for(int j=;j<m;j++)

        {

            if(a[i]>b[j])dp[][j]=(dp[][j]+s1)%md;

            else if(a[i]<b[j])dp[][j]=(dp[][j]+s2)%md;

            else

            {

                s1=(s1+dp[][j])%md;

                s2=(s2+dp[][j]+)%md;

            }

        }

        ans=(ans+s1+s2)%md;

    }

    printf("%lld\n",ans);

}

int main()

{

    int tt;scanf("%d",&tt);

    while(tt--)sol();

    return ;

}