#include <bits/stdc++.h>
//CLOCKS_PER_SEC
#define se second
#define fi first
#define ll long long
#define Pii pair<int,int>
#define Pli pair<ll,int>
#define ull unsigned long long
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define fio ios::sync_with_stdio(false);cin.tie(0);
#define db double
const double Pi=3.14159265;
const int N=1e5+10;
const ull base=163;
const int INF=0x3f3f3f3f;
const int mod=192600817;
const db eps=1e-10;
const db pi=acos(-1);
using namespace std;
ll ma[10][808],mi[10][808];
ll mam[108][808],mim[108][808];
char s[108];
ll nu[108],nuu[9];
ll dp[10][108];
ll ta[10];
ll w[10]={6,2,5,5,4,5,6,3,7,6};
int main(){
    int t,n;
    ta[1]=1;
    for(int i=2;i<=9;i++){
        ta[i]=ta[i-1]*10;
    }
    for(int k=0;k<9;k++)
            for(int kk=0;kk<108;kk++)
                dp[k][kk]=-INF;
    dp[0][0]=0;
    for(int i=1;i<=9;i++){
        for(int k=0;k<108;k++){
                for(int hh=0;hh<=9;hh++){
                    for(int jj=0;jj<=k-w[hh];jj++){
                        dp[i][jj+w[hh]]=max(dp[i-1][jj]+ta[i]*hh,dp[i][jj+w[hh]]);
                    }
                }
                ma[i][k]=dp[i][k];
            }
        }
    for(int k=0;k<9;k++)
            for(int kk=0;kk<108;kk++)
                dp[k][kk]=INF;
    dp[0][0]=0;
    for(int i=1;i<=9;i++){
        for(int k=0;k<108;k++){
                for(int hh=0;hh<=9;hh++){
                    for(int jj=0;jj<=k-w[hh];jj++){
                        dp[i][jj+w[hh]]=min(dp[i-1][jj]+ta[i]*hh,dp[i][jj+w[hh]]);
                    }
                }
                mi[i][k]=dp[i][k];
            }

        }
    cin>>t;
    while(t--){
        int cnt=0;
        scanf("%d",&n);
        scanf("%s",s);
        int now=0;
        int st=0;
        for(int i=1;i<=9;i++){
            nuu[i]=0;
        }
        for(int i=0;s[i];i++){
            if(s[i]>='0'&&s[i]<='9'){
                now++;
                st+=w[s[i]-'0'];
            }
            else{
                if(s[i]=='+'){
                    st+=2;
                }
                else{
                    st++;
                }
                nu[cnt++]=now;
                now=0;
            }
        }
        nu[cnt++]=now;
        sort(nu+1,nu+cnt,greater<int>());
        for(int j=0;j<cnt;j++){
                for(int i=0;i<=j;i++){
                    for(int kk=0;kk<=st;kk++){
                        mam[j][kk]=-INF;
                    }
                }
            for(int h=0;h<=st;h++){
                    for(int kk=0;kk<=st-h;kk++){
                        if(j==0){
                            mam[j][kk]=max(ma[nu[j]][kk],mam[j][kk]);
                        }
                        else
                        mam[j][kk+h]=max(mam[j-1][kk]+ma[nu[j]][h],mam[j][kk+h]);
                    }
                }
            }
        for(int j=cnt-1;j>=1;j--){
                for(int i=cnt-1;i>=j;i--){
                    for(int kk=0;kk<=st;kk++){
                        mim[j][kk]=INF;
                    }
                }
            for(int h=0;h<=st;h++){
                    for(int kk=0;kk<=st-h;kk++){
                        if(j==0){
                            mim[j][kk]=min(mi[nu[j]][kk],mim[j][kk]);
                        }
                        else
                        mim[j][kk+h]=min(mim[j+1][kk]+mi[nu[j]][h],mim[j][kk+h]);
                    }
                }
            }
        ll ans=0;
        int g=0;
        int h=0;
        int k=0;
        for(int i=0;i<cnt;i++){
            k+=nu[i];
        }
        for(int i=0;i<cnt;i++){
            h+=nu[i];
            g=2*i+cnt-i-1;
            for(int j=2*i;j<=st&&st-j-g>=(k-h)*2;j++){
                if(i!=cnt-1)

                ans=max(mam[i][j]-mim[i+1][st-j-g],ans);
                else
                ans=max(mam[i][j],ans);
                cout<<i<<' '<<j<<' '<<mam[i][j]<<endl;
                cout<<i+1<<' '<<st-j-g<<' '<<mim[i+1][st-j-g]<<endl;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

　　

#include <bits/stdc++.h>//CLOCKS_PER_SEC#define se second#define fi first#define ll long long#define Pii pair<int,int>#define Pli pair<ll,int>#define ull unsigned long long#define pb push_back#define ALL(x) x.begin(),x.end()#define fio ios::sync_with_stdio(false);cin.tie(0);#define db doubleconst double Pi=3.14159265;const int N=1e5+10;const ull base=163;const int INF=0x3f3f3f3f;const int mod=192600817;const db eps=1e-10;const db pi=acos(-1);using namespace std;ll ma[10][808],mi[10][808];ll mam[108][808],mim[108][808];char s[108];ll nu[108],nuu[9];ll dp[10][108];ll ta[10];ll w[10]={6,2,5,5,4,5,6,3,7,6};int main(){    int t,n;    ta[1]=1;    for(int i=2;i<=9;i++){        ta[i]=ta[i-1]*10;    }    for(int k=0;k<9;k++)            for(int kk=0;kk<108;kk++)                dp[k][kk]=-INF;    dp[0][0]=0;    for(int i=1;i<=9;i++){        for(int k=0;k<108;k++){                for(int hh=0;hh<=9;hh++){                    for(int jj=0;jj<=k-w[hh];jj++){                        dp[i][jj+w[hh]]=max(dp[i-1][jj]+ta[i]*hh,dp[i][jj+w[hh]]);                    }                }                ma[i][k]=dp[i][k];            }        }    for(int k=0;k<9;k++)            for(int kk=0;kk<108;kk++)                dp[k][kk]=INF;    dp[0][0]=0;    for(int i=1;i<=9;i++){        for(int k=0;k<108;k++){                for(int hh=0;hh<=9;hh++){                    for(int jj=0;jj<=k-w[hh];jj++){                        dp[i][jj+w[hh]]=min(dp[i-1][jj]+ta[i]*hh,dp[i][jj+w[hh]]);                    }                }                mi[i][k]=dp[i][k];            }
        }    cin>>t;    while(t--){        int cnt=0;        scanf("%d",&n);        scanf("%s",s);        int now=0;        int st=0;        for(int i=1;i<=9;i++){            nuu[i]=0;        }        for(int i=0;s[i];i++){            if(s[i]>='0'&&s[i]<='9'){                now++;                st+=w[s[i]-'0'];            }            else{                if(s[i]=='+'){                    st+=2;                }                else{                    st++;                }                nu[cnt++]=now;                now=0;            }        }        nu[cnt++]=now;        sort(nu+1,nu+cnt,greater<int>());        for(int j=0;j<cnt;j++){                for(int i=0;i<=j;i++){                    for(int kk=0;kk<=st;kk++){                        mam[j][kk]=-INF;                    }                }            for(int h=0;h<=st;h++){                    for(int kk=0;kk<=st-h;kk++){                        if(j==0){                            mam[j][kk]=max(ma[nu[j]][kk],mam[j][kk]);                        }                        else                        mam[j][kk+h]=max(mam[j-1][kk]+ma[nu[j]][h],mam[j][kk+h]);                    }                }            }        for(int j=cnt-1;j>=1;j--){                for(int i=cnt-1;i>=j;i--){                    for(int kk=0;kk<=st;kk++){                        mim[j][kk]=INF;                    }                }            for(int h=0;h<=st;h++){                    for(int kk=0;kk<=st-h;kk++){                        if(j==0){                            mim[j][kk]=min(mi[nu[j]][kk],mim[j][kk]);                        }                        else                        mim[j][kk+h]=min(mim[j+1][kk]+mi[nu[j]][h],mim[j][kk+h]);                    }                }            }        ll ans=0;        int g=0;        int h=0;        int k=0;        for(int i=0;i<cnt;i++){            k+=nu[i];        }        for(int i=0;i<cnt;i++){            h+=nu[i];            g=2*i+cnt-i-1;            for(int j=2*i;j<=st&&st-j-g>=(k-h)*2;j++){                if(i!=cnt-1)
                ans=max(mam[i][j]-mim[i+1][st-j-g],ans);                else                ans=max(mam[i][j],ans);                cout<<i<<' '<<j<<' '<<mam[i][j]<<endl;                cout<<i+1<<' '<<st-j-g<<' '<<mim[i+1][st-j-g]<<endl;            }        }        printf("%lld\n",ans);    }    return 0;}