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. 
from sys import stdin,stdout
from math import ceil

# int(stdin.readline().strip())
# stdin.readline().strip()
# list(map(int,stdin.readline().strip().split()))
# map(int,stdin.readline().strip().split())

for test in range(int(stdin.readline())):
    n, m = map(int, stdin.readline().strip().split())
    s = stdin.readline().strip()
    arr = []
    x = 0
    ma = 0
    mi = 0
    maxt = []
    mint = []
    maxp = []
    minp = []
    for i in range(n):
        if s[i] == "+":
            x += 1
        if s[i] == "-":
            x -= 1
        arr.append(x)
        ma = max(x,ma)
        mi = min(x,mi)
        maxt.append(ma)
        mint.append(mi)
    ma = -9999999
    mi = 9999999
    for i in reversed(arr):
        ma = max(i,ma)
        mi = min(i,mi)
        maxp.append(ma)
        minp.append(mi)
    maxp.reverse()
    minp.reverse()
    #print(minp)
    #print(maxp)
    #print(arr)
    for tt1 in range(m):
        l, r = map(int, stdin.readline().strip().split())
        l -= 1
        maxi = 0
        mini = 0
        ans = 1
        xx = 0
        xx1=  0

        if l > 0:
            maxi = max(maxt[l-1],maxi)
            mini = min(mini, mint[l-1])
            xx = arr[l-1]

        if r < n:
            xx1 = arr[r-1]
            dd = xx1 - xx
            maxi = max(maxi, xx + (maxp[r-1] - xx1 ))
            mini = min(mini, xx + (minp[r-1]  - xx1) )
        print(maxi-mini + 1)
        '''
        if l == r == 3:
            print("HAHHA")
            pass
        if l > 0:
            ans += (maxt[l-1] - mint[l-1] + 1 )
            if mint[l-1]<= 0 <=maxt[l-1]:
                ans -= 1
            xx = arr[l-1]
        #print(ans)

        if xx < 0 and r < n:
            xx1 = arr[r-1]

            dd = xx - xx1

            if xx1 - minp[r] > 0:
                ans += xx1 - minp[r]

            if xx1 + maxp[r] > maxt[l-1]:
                ans += maxt[l-1] - xx1 - maxp[r]
            print(ans)

        elif xx > 0 and r < n:
            xx1 = arr[r-1]
            if xx1 - maxp[r] < 0:
                ans += (maxp[r] - xx1)
            if -xx1 + minp[r] < mint[l]:
                ans += mint[l] + xx1 - minp[r]
            print(ans)

        elif xx == 0 and r < n:
            ma = maxt[l-1]
            mi = mint[l-1]
            xx1 = arr[r-1]
            #if maxp[r] >= 0 and minp[r]>=0:
            #ans += (maxp[r] - xx1)

            ans += max(0,(maxp[r] - xx1))
            ans += max(0,xx1 - minp[r])

            #if maxp[r] >0 and minp[r] > 0 or maxp[r]<0 and minp[r]<0:
            #    ans -= 1
            print(ans)
        else:
            print(ans)
        '''









