zrdbdrhbzr

/***************************************************************************
 * #######                    #                                            *
 *    #     #    #  ######   # #    #    #   ####   #    #  #    #  #      *
 *    #     #    #  #       #   #   ##   #  #       #    #  #    #  #      *
 *    #     ######  #####  #     #  # #  #   ####   ######  #    #  #      *
 *    #     #    #  #      #######  #  # #       #  #    #  #    #  #      *
 *    #     #    #  #      #     #  #   ##  #    #  #    #  #    #  #      *
 *    #     #    #  ###### #     #  #    #   ####   #    #   ####   ###### *
 ***************************************************************************/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;
#define N  205
ll dp[N][N];
ll v[5*N];
char p[5*N];
ll func(ll i,ll j)
{
    if(dp[i][j]!=-1)
        return dp[i][j];
    ll val;
    // mn=min(v[i-1]*v[i]*v[j]+func(i+1,j),v[i-1]*v[j-1]*v[j]+func(i,j-1));
    ll mx=-hell;
    if(p[i]=='+')
        val=v[i]+func(i+1,j);
    else
        val=v[i]-func(i+1,j);
    if(val>mx)
        mx=val;
    if(p[j-1]=='+')
        val=func(i,j-1)+v[j];
    else
        val=func(i,j-1)-v[j];
    if(val>mx)
        mx=val;
    rep(k,i+1,j)
    {
        if(p[k]=='+')
            val=func(i,k)+func(k+1,j);
        else
            val=func(i,k)-func(k+1,j);
        if(val>mx)
            mx=val;
        // val=v[i-1]*v[k-1]*v[j]+func(i,k-1)+func(k,j);
        // if(val<mn)
        //     mn=val;
    }
    dp[i][j]=mx;
    return mx;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int TESTS=1;
    cin>>TESTS;
    while(TESTS--)
    {
        ll n;
        cin>>n;
        rep(i,0,2*n-1)
        {
            if(i&1)
                cin>>p[i/2];
            else
                cin>>v[(i+1)/2];
        }
        rep(i,0,n)
        {
            rep(j,i,n)
            {
                if(i==j)
                    dp[i][j]=v[i];
                else if(j==i+1)
                {
                    if(p[i]=='+')
                    dp[i][j]=v[i]+v[i+1];
                    else
                    dp[i][j]=v[i]-v[i+1];
                }
                else
                    dp[i][j]=-1;
            }
        }
        cout<<func(0,n-1)<<endl;
    }
    return 0;
}