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. 
#########################################################################################################\
#########################################################################################################
###################################The_Apurv_Rathore#####################################################
#########################################################################################################
#########################################################################################################

import sys,os,io
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from sys import stdin

import math 



def ncr(n, r, p):  #using fermat's little theorem
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
                      p - 2, p)) % p

  
def primeFactors(n): 
    l = []
    while n % 2 == 0: 
        l.append(2)
        n = n / 2
          
    for i in range(3,int(math.sqrt(n))+1,2): 
          

        while n % i== 0: 
            l.append(int(i))
            n = n / i 
    if n > 2: 
        l.append(n)
    return list(set(l))
    
def power(x, y, p) : 
	res = 1
	x = x % p 
	if (x == 0) : 
		return 0
	while (y > 0) : 
		if ((y & 1) == 1) : 
			res = (res * x) % p 
		y = y >> 1	 # y = y/2 
		x = (x * x) % p 		
	return res 


def si():
    return input()

# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def prefix_sum(arr):
    r = [0] * (len(arr)+1)
    for i, el in enumerate(arr):
        r[i+1] = r[i] + el
    return r

def divideCeil(n,x):
    if (n%x==0):
        return n//x
    return n//x+1

def ii():
    return int(input())

def li():
    return list(map(int,input().split()))

def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')


if(os.path.exists('input.txt')):
    sys.stdin = open("input.txt","r")
    sys.stdout = open("output.txt","w")





# python3 implementation of above approach
from math import ceil,log,floor

# Each segment of the segment tree would be a set
# to maintain distinct elements
segment=[[] for i in range(1000)]

# Build the segment tree
# i denotes current node, s denotes start and
# e denotes the end of range for current node
def build(i, s, e, arr):

	# If start is equal to end then
	# append the array element
	if (s == e):
		segment[i].append(arr[s])
		return

	# Else divide the range into two halves
	# (start to mid) and (mid+1 to end)
	# first half will be the left node
	# and the second half will be the right node
	build(2 * i, s, (s + e) // 2, arr)
	build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

	# Insert the sets of right and left
	# node of the segment tree
	segment[i].append(segment[2 * i])

	segment[i].append(segment[2 * i + 1])

# Query in an range a to b
def query(node, l, r, a, b):
	left, right, result=[],[],[]

	# If the range is out of the bounds
	# of this segment
	if (b < l or a > r):
		return result

	# If the range lies in this segment
	if (a <= l and r <= b):
		return segment[node]

	# Else query for the right and left
	# leaf node of this subtree
	# and append them into the set
	left = query(2 * node, l, (l + r) // 2, a, b)
	result.append(left)

	right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
	result.append(right)

	# Return the result
	return result
def answer(ans):
	d = {}
	for i in str(ans):
		if i not in ['[',',',']',' ']:
			d[i]=1
	return len(d)

# Initialize the segment tree
def init(n):
	
	# Get the height of the segment tree
	h = ceil(log(n, 2))
	h = (2 * (pow(2, h))) - 1

# Function to get the result for the
# subarray from arr[l] to arr[r]

def wi(n): sys.stdout.write(str(n) + '\n')

t = int(input())
for _ in range(t):
    n,k = list(map(int,stdin.readline().split()))
    s = stdin.readline().strip()
    Max = 0 ; Min =0 ; curr = 0
    premax = [0]*(n+1) ; premin = [0]*(n+1)
    rpremax = [0]*(n+1) ; rpremin = [0]*(n+1)
    end = [0]*(n+1)
    for i in range(n):
        if s[i]=='+':
            curr+=1
        else:
            curr-=1
        
        Max = max(Max,curr)
        premax[i+1] = Max
        Min = min(Min,curr)
        premin[i+1] = Min
        end[i+1] = curr
    Max = 0; Min = 0; curr = 0
    rend = [0]*(n+1)
    for i in range(n-1,-1,-1):
        if s[i]=='-':
            curr+=1
        else:
            curr-=1
        
        Max = max(Max,curr)
        rpremax[i] = Max
        Min = min(Min,curr)
        rpremin[i] = Min
        rend[i] = curr
    
    for i in range(k):
        l,r = list(map(int,stdin.readline().split()))
        l-=1
        # print(l,r)
        # print(premax,rpremax,end,rend)
        postmax = end[l] + rpremax[r] - rend[r]
        postmin = end[l] + rpremin[r]-rend[r]
        wi(max(premax[l],postmax)-min(premin[l], postmin )+1)
        




    
    






