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 int long long


#define pie 3.141592653589793238462643383279
#define M1 1000000007
#define M2 998244353
#define ll long long
#define pb push_back
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rsort(x) sort(x,greater<int> ())
#define endl "\n"
#define gcd __gcd
#define lcm(a,b) (a*b)/gcd(a,b)
#define deci(n) fixed << setprecision(n)
#define test() int test_case;cin >> test_case;while (test_case--)
#define sp " "
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define max4(a,b,c,d) max(a,max3(b,c,d))
#define min4(a,b,c,d) min(a,min3(b,c,d))
#define max5(a,b,c,d,e) max(max4(a,b,c,d),e)
#define min5(a,b,c,d,e) min(min4(a,b,c,d),e)


typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef map<int,int> mi;

/*Power function starts*/
int Power(int a,int n,int mod){
    int res=1;
    while(n){
        if(n%2!=0){
            res=((res%mod)*(a%mod))%mod;
            n--;
        }
        else
        {
            a=((a%mod)*(a%mod))%mod;
            n/=2;
        }
    }
    return res;
}

/*Power function ends*/


/* Prime Checker starts */
bool isPrime(int n) 
{ 
    // Corner cases 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
  
    // This is checked so that we can skip 
    // middle five numbers in below loop 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
  
    return true; 
} 
/* Prime Checker ends */

/* Sum of Digits starts */
int getSum(int n) 
{  
   int sum = 0; 
   while (n != 0) 
   { 
       sum = sum + n % 10; 
       n = n/10; 
   } 
   return sum; 
} 
/* Sum of digits ends */

/* Ceiling function starts */
int myceil(int n,int x)
{
    int y;
    if(n%x==0)
    {
        y=n/x;
        return y;
    }
    else
    {
        y=n/x+1;
        return y;
    }
    
}
/* ceiling function ends */


int md=M1;
vi fact, inv;
 
void inverse(ll n)
{if(n>=inv.size()){ll size=inv.size();size=size==0? 1:size;
inv.resize(n + 1);inv[0] = 1;
for (ll i = size; i <= n; i++)inv[i] = Power(fact[i], md-2, md);}}
 
void factorial(ll n)
{if(n>=fact.size()){ll size=fact.size();size=size==0? 1:size;
fact.resize(n + 1);fact[0] = 1;for (ll i = size; i <= n; i++)
fact[i] = (fact[i - 1] * i) % md;
}}
 
ll ncr(ll n, ll r) { return (((fact[n] * inv[r]) % md) * inv[n - r]) % md; }

#define MAX_SIZE 1300000
int primes[MAX_SIZE];
// Function to generate N prime numbers using  
// Sieve of Eratosthenes 
void Sieve()  
{  
    bool IsPrime[MAX_SIZE];  
    memset(IsPrime, true, sizeof(IsPrime));  
    
    for (int p = 2; p * p < MAX_SIZE; p++)  
    {  
        if (IsPrime[p] == true)  
        {
            for (int i = p * p; i <  MAX_SIZE; i += p)  
                IsPrime[i] = false;  
        }  
    }  
    int index = 0;
    for (int p = 2; p < MAX_SIZE; p++)  
       if (IsPrime[p])   // Store all prime numbers  
            {
                primes[index] = p;
                index++;
            }
             
}   
// 15 = 24*0 + 15
// 24 = 15*1 + 9
// 15 = 9*1 +6
// 9 = 6*1 +3;
// 6 = 3*2 +0;

int gcd(int a,int b){
    if(b==0){
        return a;
    }
    int ans = gcd(b,a%b);
    return ans;
}


//********************THE END OF TEMPLATES*******************//

bool helper(pair<int,int> p1,pair<int,int> p2){
    if(p1.first==p2.first){
        return p1.second<p2.second;
    }
    return p1.first<p2.first;
}

void swap(int* a,int* b){
    int temp = *a;
    *a=*b;
    *b=temp;
}
// 11 9 and x=10
void solve(){
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    int x = 0;
    vector<pair<pair<int,int>,int>> prefix(n),suffix(n);
    int mn=0,mx=0;
    for(int i=0;i<n;i++){
        if(s[i]=='+')x++;
        else x--;
        mn = min(mn,x);
        mx = max(mx,x);
        prefix[i] = {{mn,mx},x};
    }
    // cout<<"prefixes"<<endl;
    // cout<<"min max t"<<endl;
    // for(int i=0;i<n;i++){
    //     cout<<prefix[i].first.first<<"    "<<prefix[i].first.second<<"   "<<prefix[i].second<<endl;
    // }

    mn = 0,mx = 0;
    x = 0;
    for(int i = n-1;i>=0;i--){
        if(s[i]=='+')x++;
        else x--;
        mn = s[i]=='+'?(min(mn+1,(int)0)):mn-1;
        mx = s[i]=='+'?mx+1:max(mx-1,(int)0);
        suffix[i] = {{mn,mx},x};
    }
    // cout<<"sufixes"<<endl;
    // cout<<"min max t"<<endl;
    // for(int i=0;i<n;i++){
    //     cout<<suffix[i].first.first<<"    "<<suffix[i].first.second<<"   "<<suffix[i].second<<endl;
    // }
    while(m--){
        int l,r;
        cin>>l>>r;
        l--;r--;
        if(l==0&&r==n-1){
            cout<<1<<endl;
        }
        else if(l==0){
            int ans = suffix[r+1].first.second - suffix[r+1].first.first + 1;
            cout<<ans<<endl;
        }
        else if(r==n-1){
            int ans = prefix[l-1].first.second - prefix[l-1].first.first + 1;
            cout<<ans<<endl;
        }
        else{
            int l1 = prefix[l-1].first.first;
            int r1 = prefix[l-1].first.second;
            int t = prefix[l-1].second;
            int l2 = t + suffix[r+1].first.first;
            int r2 = t + suffix[r+1].first.second;
            //cout<<"(l1,r1)-->("<<l1<<","<<r1<<")"<<endl;
            //cout<<"(l2,r2)-->("<<l2<<","<<r2<<")"<<endl;
            if(min(r1,r2)<max(l1,l2)){
                int ans = r2-l2 + r1-l1 + 2;
                cout<<ans<<endl;
            }
            else{
                cout<<max(r1,r2)-min(l1,l2)+1<<endl;
            }
        }
    }
}


int32_t main()
{
    fast();
    test(){
        solve();
    }
    return 0;
}



/*
x = 5
0 2 3 4 5 6 7 8 9 3 ........if less than 9 than -1
0 2 3 4 5 5 6 7 8 9
*/