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>
using namespace std;
#define endl "\n"
#define int long long 
#define rep(i,j,k) for(int i=j;i<k;i+=1)
#define rrep(i,j,k) for(int i=n-1;i>=0;i-=1)
#define sorti(v) sort(v.begin(),v.end())
#define sortd(v) sort(v.begin(),v.end(),greater<int>())
#define mm map<int,int>
#define vv vector<int>
#define tmm map<int,map<int,int>>
#define trav(a, x) for(auto& a : x)
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(v) v.begin(),v.end()
#define pb push_back
#define alot(x,y) memset(x,y,sizeof(x))
#define pii pair<int,int>
#define code ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int MOD=1e9+7;
const double pi=acos(-1.0);
/*memset(array_name,value_to_be_intialized,sizeof(array_name));
 __builtin_popcount(n) count no of set bit in number n
next_permutation(s.begin(),s.end());
int binpow(int a,int b){
    int res=1;
    while(b>0){
        if(b&1)res*=a;
        a*=a;
        b>>=1;
        
    }
    return res;
}
// lower_bound==> if the element is present it return its first occurence else 1st element which is greater than 
// upper_bound==> it will always return iterator to element which is greater than searched element
*/
int n;
int a[300005];
int segmn[800045];
int segmx[800045];
int buildmn(int i,int l,int r){
    if(l==r){
        return segmn[i]=a[l];
    }
    int mid=(l+r)/2;
    int p=buildmn(2*i+1,l,mid);
    int q=buildmn(2*i+2,mid+1,r);
    return segmn[i]=min(p,q);
}
int buildmx(int i,int l,int r){
    if(l==r){
        return segmx[i]=a[l];
    }
    int mid=(l+r)/2;
    int p=buildmx(2*i+1,l,mid);
    int q=buildmx(2*i+2,mid+1,r);
    return segmx[i]=max(p,q);
}
int solvemn(int i,int left,int right,int l,int r){
    if(right<l || left>r){
        return MOD*100000;
    }
    if(left<=l && right>=r){
       // cout<<"segment=>";
       // cout<<l<<"="<<r<<"=>"<<i<<" "<<segmn[i]<<"\n";
        return segmn[i];
    }
    int mid=(l+r)/2;
    int p=solvemn(2*i+1,left,right,l,mid);
    int q=solvemn(2*i+2,left,right,mid+1,r);
    return min(p,q);
}
int solvemx(int i,int left,int right,int l,int r){
    if(right<l || left>r){
        return -1*MOD*100000;
    }
    if(left<=l && right>=r){
        return segmx[i];
    }
    int mid=(l+r)/2;
    int p=solvemx(2*i+1,left,right,l,mid);
    int q=solvemx(2*i+2,left,right,mid+1,r);
    return max(p,q);
}
int32_t main ()
{
     code;
    int tt;
    cin>>tt;
    //tt=1;
    while(tt--){
        int q;
        cin>>n>>q;
        string s;
        cin>>s;
        int sum=0;
        mm pref;
        for(int i=0;i<n;i++){
            if(s[i]=='-')sum-=1;
            else if(s[i]=='+')sum+=1;
            a[i]=sum;
            pref[i]=sum;
        }
        for(int i=0;i<n;i++){
           // cout<<a[i]<<" ";
        }
       // cout<<'\n';
        buildmn(0,0,n-1);
        buildmx(0,0,n-1);
        while(q--){
            int l,r;
            cin>>l>>r;
            if(l==1 && r==n){
                cout<<"1\n";
            }
            else{
            int sub=pref[r-1]-pref[l-2];
            l-=2;
            r;
           // sub=0;
            int a=solvemn(0,0,l,0,n-1);
            int b=solvemx(0,0,l,0,n-1);
            int c=solvemn(0,r,n-1,0,n-1)+-1*sub;
            int d=solvemx(0,r,n-1,0,n-1)+-1*sub;
            if(l>=0){
                a=min(a,0LL);
                b=max(b,0LL);
            }
            else{
                c=min(c,0LL);
                d=max(d,0LL);
            }
            //cout<<"sub="<<sub<<"\n";
          // cout<<l<<" "<<r<<"=>";
            //cout<<a<<" "<<b<<" "<<c<<" "<<d<<"\n";
            int p=MOD;
            int q=-1*MOD;
            if(a<=MOD){
                p=min(p,a);
            }
            if(c<=MOD){
                p=min(p,c);
            }
            if(b>=-1*MOD){
                q=max(b,q);
            }
            if(d>=-1*MOD){
                q=max(d,q);
            }
            cout<<q-p+1<<"\n";
                
            }
          
        }
        
        
    
    }
    return 0;
    
}