You are given a program that consists of n instructions. Initially a single variable x is assigned to 0. Afterwards, the instructions are of two types: 

  * increase x by 1; 
  * decrease x by 1. 



You are given m queries of the following format: 

  * query l r — how many distinct values is x assigned to if all the instructions between the l-th one and the r-th one inclusive are ignored and the rest are executed without changing the order? 

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

Then the description of t testcases follows.

The first line of each testcase contains two integers n and m (1 ≤ n, m ≤ 2 ⋅ 10^5) — the number of instructions in the program and the number of queries.

The second line of each testcase contains a program — a string of n characters: each character is either '+' or '-' — increment and decrement instruction, respectively.

Each of the next m lines contains two integers l and r (1 ≤ l ≤ r ≤ n) — the description of the query.

The sum of n over all testcases doesn't exceed 2 ⋅ 10^5. The sum of m over all testcases doesn't exceed 2 ⋅ 10^5. 

Output

For each testcase print m integers — for each query l, r print the number of distinct values variable x is assigned to if all the instructions between the l-th one and the r-th one inclusive are ignored and the rest are executed without changing the order.

Example

Input


2
8 4
-+--+--+
1 8
2 8
2 5
1 1
4 10
+-++
1 1
1 2
2 2
1 3
2 3
3 3
1 4
2 4
3 4
4 4


Output


1
2
4
4
3
3
4
2
3
2
1
2
2
2

Note

The instructions that remain for each query of the first testcase are: 

  1. empty program — x was only equal to 0; 
  2. "-" — x had values 0 and -1; 
  3. "---+" — x had values 0, -1, -2, -3, -2 — there are 4 distinct values among them; 
  4. "+--+--+" — the distinct values are 1, 0, -1, -2. 
#include<bits/stdc++.h>
#define fore(start,i,end) for(int i = start; i <= end; i++)
#define dbg(x)  #x << "=" << x << " "
#define dbg2(x,y)  "{" << x << "," << y << "} "
#define dbg3(x,y,k) "{" << x << "," << y << "," << k << "} "
#define dbg4(x,y,k,j) "{" << x << "," << y << "," << k << " , " << j << "} "

#define ll long long
#define f1 first
#define f2 second
#define inf 1000000005
#define debug_st(st) if (true) {cout << #st << " : "; stack<int> s123; while (!s123.empty()) cout << s123.top() << " ", s123.pop(); cout << "\n";}
#define debug_a(a,n) cout << #a << " : "; for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << "\n";
#define debug_m(a,n,m) cout << #a << " :\n"; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++) cout << a[i][j] << " "; cout << "\n"; }cout << "\n";
#define debug_v(v) cout << #v << " : "; for(auto k : v) cout << k << " "; cout << "\n";
#define debug_s(s) cout << #s << " : "; for (auto k : s) cout << k < " "; cout << "\n";
#define debug_s2(s) cout << #s << " : "; for(auto k : s) cout << dbg2((*k).first,(*k).second); cout << "\n";
#define nmax 500005


using namespace std;

ifstream in("in.in");
ofstream out("out.out");

int t,n,m,a[nmax];

struct nod
{
    int Max,Min,sum,lazy;
    nod()
    {
        Max = inf;
        Min = -inf;
        sum = lazy = 0;
    }
    nod(int a, int b, int c, int d)
    {
        Max = Min = sum  = lazy = 0;
    }
};

nod aint[nmax];
nod Merge(nod st, nod dr)
{
    nod tnode;
    tnode.Max = max(st.Max , dr.Max);
    tnode.Min = min(st.Min, dr.Min);
    tnode.sum = st.sum + dr.sum;
    tnode.lazy = 0;
    return tnode;
}

void update_nod(int nod, int st, int dr, int sum) //pentru cand ii dai un lazy in Plus
{
    aint[nod].lazy += sum;
    aint[nod].sum += sum * (dr - st + 1);

    aint[nod].Max += sum;
    aint[nod].Min += sum;
}
void update(int nod , int st, int dr, int qst, int qdr, int sum)
{
    if (qst <= st && dr <= qdr)
    {
        update_nod(nod , st , dr , sum);
        return;
    }

    int copil_st = nod * 2;
    int copil_dr = nod * 2 + 1;
    int mij = (st + dr) / 2;

    if (aint[nod].lazy != 0) //dam mai departe lazy-ul
    {
        update_nod(copil_st , st  , mij , aint[nod].lazy);
        update_nod(copil_dr , mij + 1 , dr , aint[nod].lazy);
        aint[nod].lazy = 0;
    }

    if (qst <= mij)
    {
        update(copil_st , st , mij , qst , qdr , sum);
    }
    if (qdr > mij)
    {
        update(copil_dr , mij + 1, dr , qst , qdr , sum);
    }
    //recalculam nodul
    aint[nod] = Merge(aint[copil_st] , aint[copil_dr]);
}

nod query(int nod, int st, int dr, int qst, int qdr) //dam un nod care sa cuprinda intervalul ala
{
    if (qst <= st && dr <= qdr)
    {
        return aint[nod];
    }

    int copil_st = nod * 2;
    int copil_dr = nod * 2 + 1;
    int mij = (st + dr) / 2;

    if (aint[nod].lazy != 0) //dam mai departe lazy-ul
    {
        update_nod(copil_st , st  , mij , aint[nod].lazy);
        update_nod(copil_dr , mij + 1 , dr , aint[nod].lazy);
        aint[nod].lazy = 0;
    }

    bool este_st, este_dr;
    este_st = (qst <= mij);
    este_dr = (qdr > mij);

    if (este_st == 1 && este_dr == 1)
    {
        return Merge(query(copil_st , st , mij , qst , qdr) , query(copil_dr , mij + 1, dr, qst,qdr));
    }
    else if(este_st == 1)
    {
        return query(copil_st ,  st , mij , qst, qdr);
    }
    else if (este_dr == 1)
    {
        return query(copil_dr , mij + 1, dr , qst, qdr);
    }
}
void init_aint(int nod, int st ,int dr)
{
    if (st == dr)
    {
        aint[nod].sum = aint[nod].Max = aint[nod].Min = a[st];
        aint[nod].lazy = 0;

       // cout << dbg(nod) << " sum = " << aint[nod].sum << " Max = " << aint[nod].Max << " Min = " << aint[nod].Min << " st = " << st << " " << dbg(dr) << "\n";
        return;
    }

    int cop_st = nod * 2;
    int cop_dr = nod * 2 + 1;
    int mij = (st + dr) / 2;
    init_aint(cop_st , st , mij);
    init_aint(cop_dr , mij + 1 , dr);
    aint[nod] = Merge(aint[cop_st] , aint[cop_dr]);
   // cout << dbg(nod) << " sum = " << aint[nod].sum << " Max = " << aint[nod].Max << " Min = " << aint[nod].Min << " st = " << st << " "<< dbg(dr) << "\n";


}
int main()
{int i;
    cin >> t;
   // cout << dbg(t) << "\n";
    while (t--)
    {
        cin >> n >> m;
        //cout << dbg(n) << dbg(m) << "\n";
        for (i = 1; i <= n; i++)
        {char car;
            cin >> car;
            if (car == '+')
                a[i] = 1;
            else
                a[i] = -1;
        }
       // debug_a(a , n);
        for (i = 1; i <= n; i++)
            a[i] += a[i - 1];
       // cout << "acum a e sume de prefix\n";
        //debug_a(a , n);

        init_aint(1 , 1 , n);


        /*int l,r,tip,s;
        do
        {
            cin >> tip >> l >> r;
            if (tip == 0)
                cout << "sum = " << query(1 , 1 , n ,l , r).sum << " min = " <<  query(1 , 1 , n ,l , r).Min << " max = " <<  query(1 , 1 , n ,l , r).Max << "\n";
            else {
                cin >> s;
                cout << "updatam " << l << " " << r << " cu " << s << "\n new a: ";
                update(1 , 1 , n ,l , r , s);
                for (int i = 1; i <= n; i++)
                    cout << query(1 , 1 , n , i , i).sum << " ";
                cout << "\n";
            }
        } while(l != 123);*/

        for (i = 1; i <= m; i++)
        {int l,r;
            cin >> l >> r;          //  cout << dbg(l) << dbg(r) << "\n";

            if (l == 1 && r == n) {
                cout << "1\n";
                continue;
            }
            if (l == 1)
            {
                //cout << dbg(query(1 , 1 , n , r + 1, n).Max) << dbg(query(1 , 1, n , r + 1, n).Min) << "\n";
               // cout << dbg(query(1 , 1 , n , r + 1, n).Max) << dbg(query(1 , 1, n , r + 1, n).Min) << "\n";

                int int_sum = query(1 , 1 , n , r, r).sum;
                update(1 , 1 , n, r + 1 , n , -int_sum);
                cout << max(0 , query(1 , 1 , n , r + 1, n).Max) - min(0 , query(1 , 1, n , r + 1, n).Min) + 1  << "\n";
                update(1 , 1 , n , r + 1, n, int_sum);

                continue;
            }
            if (r == n)
            {
               // cout << dbg(query(1, 1, n, 1, l - 1).Max) << dbg(query(1 , 1,  n , 1 , l - 1).Min) << "\n";
               // cout << dbg(query(1, 1, n, 1, l - 1).Max) << dbg(query(1 , 1,  n , 1 , l - 1).Min) << "\n";
                cout <<  max(0 , query(1, 1, n, 1, l - 1).Max) - min(0 , query(1 , 1,  n , 1 , l - 1).Min) + 1 << "\n";
                continue;
            }

            int int_sum = query(1 , 1 , n , r, r).sum - query(1 , 1 , n , l - 1 , l - 1).sum;
            update(1 , 1 , n, r + 1 , n , -int_sum);

           // cout << "max : " << max(query(1, 1, n, 1, l - 1).Max , query(1 , 1 , n , r + 1, n).Max) << " min : " << min(query(1 , 1,  n , 1 , l - 1).Min , query(1 , 1, n , r + 1, n).Min) << "\n";

            cout << max(0 , max(query(1, 1, n, 1, l - 1).Max , query(1 , 1 , n , r + 1, n).Max))
            - min(0 , min(query(1 , 1,  n , 1 , l - 1).Min , query(1 , 1, n , r + 1, n).Min)) + 1 << "\n";

            update(1 , 1 , n , r + 1, n, int_sum);
        }
    }
}



