/*

正解O(n)尺取法orz

我写的二分答案。本来以为会被卡成暴力分......

这个-'0'-48是我写的吗........我怎么不记得...

*/

#include<bits\stdc++.h>

#define N 1000001

#define inf 0x3f3f3f3f

using namespace std;

int n,m,ans,cnt,flag;

char s1[N],s2[N],cur[N];

int vis[][N],v[];

bool judge(int l,int len)

{

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

      if(vis[cur[i]-''-][l+len-]-vis[cur[i]-''-][l-]==) return false;

    return true;

}

int main()

{

    freopen("english.in","r",stdin);

    freopen("english.out","w",stdout);

    scanf("%d",&n);

    scanf("%s",s1);

    for(int i=;i<n;i++) vis[s1[i]-''-][i]=;

    for(int j='a';j<='z';j++) for(int i=;i<=n;i++)

    {

        if(s1[i]==j) vis[j-''-][i]=vis[j-''-][i-]+;

        else vis[j-''-][i]=vis[j-''-][i-];

    }

    scanf("%s",s2);

    int len=strlen(s2);

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

      if(!v[s2[i]-''-]) v[s2[i]-''-]=,cur[++cnt]=s2[i];

    for(int i=n-len;i<n;i++) if(s1[i]!=s2[i]) flag=;

    if(!flag)

    {

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

        return ;

    }

    int l,r,mid;ans=n;

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

    {

        l=,r=ans;

        while(l<=r)

        {

            int mid=(l+r)>>;

            if(judge(i,mid)) ans=min(ans,mid),r=mid-;

            else l=mid+;

        }

        if(ans==len) break;

    }

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

    fclose(stdin);fclose(stdout);

    return ;

}

/*

首先如果数列最大最小差大于1是显然不行

如果都为n-1显然可以

其余情况嘛

有n个人，A说，你们一群人中我看到了3种颜色。B说，我比你牛逼，我看到了四种！

这说明了什么？想一想就能明白，说明颜色一定有4种，并且A头顶上的颜色一定跟所有人不同。

因此所有较小的数都是一种与众不同的颜色，较大的数这个集合里肯定至少两两相同。

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 1000007

using namespace std;

int n,x,y,ans,cnt1,cnt2;

int a[N];

inline int read()

{

    int x=,f=;char c=getchar();

    while(c>''||c<''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int main()

{

    freopen("hat.in","r",stdin);

    freopen("hat.out","w",stdout);

    int T;T=read();

    while(T--)

    {

        n=read();a[]=read();cnt1=;cnt2=;

        x=;y=;

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

        {

            a[i]=read();

            if(a[i]!=a[i-]) x=a[i],y=a[i-];

        }

        if(x== && y==){printf("Yes\n");continue;}

        if(x>y) swap(x,y);

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

        {

            if(a[i]==x) cnt1++;

            if(a[i]==y) cnt2++;

        }

        if(cnt1+cnt2!=n)

        {

            printf("Yes\n");

            continue;

        }

        if(cnt2==) printf("Yes\n");

        else if(cnt2/>=y-cnt1) printf("No\n");

        else printf("Yes\n");

    }

    fclose(stdin);fclose(stdout);

    return ;

}

/*

严格次小生成树模板

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define Maxn 300010

using namespace std;

struct edge

{

    int to,w,next;

} p[Maxn];

int head[Maxn/],tot;

void addedge(int a,int b,int c)

{

    p[tot].to=b;

    p[tot].w=c;

    p[tot].next=head[a];

    head[a]=tot++;

}

struct line

{

    int u,v,w;

    bool operator<(const line &a)const

    {

        return w<a.w;

    }

} q[Maxn];

int vis[Maxn];

int fa[Maxn/];

int findset(int x)

{

    return fa[x]==x?x:(fa[x]=findset(fa[x]));

}

int unionset(int a,int b)

{

    return fa[findset(a)]=findset(b);

}

int dep[Maxn/];

int f[Maxn/][],g[Maxn/][],h[Maxn/][];

void dfs(int u,int fa)

{

    f[u][]=fa;

    dep[u]=dep[fa]+;

    for(int i=head[u]; i!=-; i=p[i].next)

    {

        int v=p[i].to;

        if(v!=fa)

        {

            g[v][]=p[i].w;

            h[v][]=-;

            dfs(v,u);

        }

    }

}

void ck1(int &a,int &b,int c,int d,int e,int f)

{

    if(c==e)

    {

        a=c;

        b=max(d,f);

        return;

    }

    if(c>e)

    {

        swap(c,e);

        swap(d,f);

    }

    a=e;

    b=max(c,f);

}

int ck2(int lx,int ln,int w)

{

    if(w==lx) return w-ln;

    return w-lx;

}

void ck3(int &lx,int &ln,int u,int t)

{

    if(g[u][t]==lx) ln=max(ln,h[u][t]);

    else if(g[u][t]<lx) ln=max(ln,g[u][t]);

    else

    {

        ln=(lx,h[u][t]);

        lx=g[u][t];

    }

}

void init(int n)

{

    dfs(,);

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

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

        {

            if(!f[i][j]) f[i][j+]=;

            else

            {

                f[i][j+]=f[f[i][j]][j];

                ck1(g[i][j+],h[i][j+],g[i][j],h[i][j],g[f[i][j]][j],h[f[i][j]][j]);

            }

        }

}

int LCA(int u,int v,int w)

{

    int lx=-,ln=-;

    if(dep[u]<dep[v]) swap(u,v);

    int df=dep[u]-dep[v],t=;

    while(df)

    {

        if(df&)

        {

            ck3(lx,ln,u,t);

            u=f[u][t];

        }

        t++;

        df>>=;

    }

    if(u==v) return ck2(lx,ln,w);

    for(int i=; i>=; i--)

    {

        if(f[u][i]!=f[v][i])

        {

            ck3(lx,ln,u,i);

            ck3(lx,ln,v,i);

            u=f[u][i];

            v=f[v][i];

        }

    }

    ck3(lx,ln,u,);

    ck3(lx,ln,v,);

    return ck2(lx,ln,w);

}

int main()

{

    freopen("tree.in","r",stdin);

    freopen("tree.out","w",stdout);

    int n,m;

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

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

        scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);

    sort(q,q+m);

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

    memset(head,-,sizeof head);

    memset(vis,,sizeof vis);

    tot=;

    int cnt=;

    long long ans=;

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

    {

        int u=q[i].u,v=q[i].v;

        if(findset(u)==findset(v)) continue;

        unionset(u,v);

        vis[i]=;

        addedge(u,v,q[i].w);

        addedge(v,u,q[i].w);

        ans+=q[i].w;

        if(++cnt==n-) break;

    }

    init(n);

    int z=0x3f3f3f3f;

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

        if(!vis[i]) z=min(z,LCA(q[i].u,q[i].v,q[i].w));

    cout<<ans+z<<endl;

    return ;

}