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;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

// change ld to db if neccesary
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pld;

typedef set<int> si;
typedef set<ll> sl;
typedef set<ld> sld;
typedef set<str> ss;
typedef set<pi> spi;
typedef set<pl> spl;
typedef set<pld> spld;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vld;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<si> vsi;
typedef vector<sl> vsl;
typedef vector<pld> vpld;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define forr(i,a,b) for (int i = (a); i < (b); i++)
#define ford(i,a,b) for (int i = (a)-1; i >= (b); i--)
#define trav(a,x) for (auto& a: x)

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
int pct(int x) { return __builtin_popcount(x); }
int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x))
int fstTrue(function<bool(int)> f, int lo, int hi) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true
		int mid = (lo+hi)/2;
		f(mid) ? hi = mid : lo = mid+1;
	}
	return lo;
}

const ll MOD = 1e9+7;
const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
bool sortcol(const vl& v1, const vl& v2) {return v1[1] < v2[1];}
bool sortpair(const pi& p1, const pi& p2) {return p1.f < p2.f;}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<long long unsigned> distribution(0,10);

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
// void __print(mi x) {cerr << x;}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

const int mxN = 2e5+5;
int n, m, st2[4*mxN], st3[4*mxN], psum[mxN];
str s;

// void update(int i, int x, int lo=0, int hi=-1, int node=0) {
// 	if (hi == -1) hi = n - 1;
// 	if (hi < i || lo > i) return;
// 	if (lo == hi) { st[node] += x; return; }
// 	int mid = (lo + hi) / 2;
// 	update(i, x, lo, mid, 2 * node + 1);
// 	update(i, x, mid + 1, hi, 2 * node + 2);
// 	st[node] = st[2 * node + 1] + st[2 * node + 2];
// }
// // for min segtree, remember to return INF instead of 0
// int query(int s, int e, int lo=0, int hi=-1, int node=0) {
// 	if (hi == -1) hi = n - 1;
// 	if (hi < s || lo > e) return 0;
// 	if (lo >= s && hi <= e) return st[node];
// 	int mid = (lo + hi) / 2;
// 	return query(s, e, lo, mid, 2 * node + 1) + 
// 			query(s, e, mid + 1, hi, 2 * node + 2);
// }
void update2(int i, int x, int lo=0, int hi=-1, int node=0) {
	if (hi == -1) hi = n - 1;
	if (hi < i || lo > i) return;
	if (lo == hi) { st2[node] += x; return; }
	int mid = (lo + hi) / 2;
	update2(i, x, lo, mid, 2 * node + 1);
	update2(i, x, mid + 1, hi, 2 * node + 2);
	st2[node] = max(st2[2 * node + 1], st2[2 * node + 2]);
}
// for min segtree, remember to return INF instead of 0
int query2(int s, int e, int lo=0, int hi=-1, int node=0) {
	if (hi == -1) hi = n - 1;
	if (hi < s || lo > e) return -1e9;
	if (lo >= s && hi <= e) return st2[node];
	int mid = (lo + hi) / 2;
	return max(query2(s, e, lo, mid, 2 * node + 1), 
			query2(s, e, mid + 1, hi, 2 * node + 2));
}
void update3(int i, int x, int lo=0, int hi=-1, int node=0) {
	if (hi == -1) hi = n - 1;
	if (hi < i || lo > i) return;
	if (lo == hi) { st3[node] += x; return; }
	int mid = (lo + hi) / 2;
	update3(i, x, lo, mid, 2 * node + 1);
	update3(i, x, mid + 1, hi, 2 * node + 2);
	st3[node] = min(st3[2 * node + 1], st3[2 * node + 2]);
}
// for min segtree, remember to return INF instead of 0
int query3(int s, int e, int lo=0, int hi=-1, int node=0) {
	if (hi == -1) hi = n - 1;
	if (hi < s || lo > e) return 1e9;
	if (lo >= s && hi <= e) return st3[node];
	int mid = (lo + hi) / 2;
	return min(query3(s, e, lo, mid, 2 * node + 1), 
			query3(s, e, mid + 1, hi, 2 * node + 2));
}
void solve() {
	cin >> n >> m >> s;
	// forr(i,0,s.length()) {
	// 	if (s[i] == '-') {
	// 		update(i,-1);
	// 		// update2(i,-1);
	// 		// update3(i,-1);
	// 	} else {
	// 		update(i,1);
	// 		// update2(i,1);
	// 		// update3(i,1);
	// 	}
	// }
	int curr = 0;
	forr(i,0,s.length()) {
		if (s[i] == '-') {
			curr--;
		} else curr++;
		psum[i] = curr;
		update2(i,curr);
		update3(i,curr);
	}
	forr(i,0,m) {
		int l, r; cin >> l >> r; l--, r--;
		int mn = 0, mx = 0;
		int sum = psum[r] - (r ? psum[l-1] : 0);
		// int sum = query(l,r);
		if (l) ckmax(mx,query2(0,l-1));
		if (l) ckmin(mn,query3(0,l-1));
		if (r+1 <= n-1) ckmax(mx,query2(r+1,n-1)-sum);
		if (r+1 <= n-1) ckmin(mn,query3(r+1,n-1)-sum);
		dbg(sum,mx,mn);
		cout << mx-mn+1 << "\n";
		assert(mx >= mn);
	}
	forr(i,0,min(5*n,mxN)) {
		// st[i] = 0;
		st2[i] = 0;
		st3[i] = 0;
	}
	// forr(i,0,n) {
	// 	update(i,-query(i,i));
	// 	update2(i,-query2(i,i));
	// 	update3(i,-query3(i,i));
	// }
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	int tc = 1;
	cin >> tc;
	while (tc--) solve();
}