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. 
import sys
import math
from collections import defaultdict

MAXNUM = math.inf
MINNUM = -1 * math.inf
ASCIILOWER = 97
ASCIIUPPER = 65


def getInt():
    return int(sys.stdin.readline().rstrip())


def getInts():
    return map(int, sys.stdin.readline().rstrip().split(" "))


def getString():
    return sys.stdin.readline().rstrip()


def printOutput(ans):
    sys.stdout.write()
    pass


def solve(ops, queries):
    prefixdp = [0 for _ in range(len(ops) + 1)]
    prefixdp[0] = (0, 0, 0)  # highest, lowest, cur
    suffixdp = [0 for _ in range(len(ops) + 1)]

    for i in range(len(ops)):
        highest, lowest, cur = prefixdp[i]
        if ops[i] == "+":
            cur += 1
        else:
            cur -= 1
        prefixdp[i + 1] = (max(highest, cur), min(lowest, cur), cur)
    #print(prefixdp)

    # suffix, calculating max displacement by looking at cur value of prefix
    # assumption is that we are starting r-side from square i (looping from back)
    # we do this by looking at the cur of the prefixdp and calculating
    # a relative minimum and maximum
    cur = prefixdp[-1][
        -1
    ]  # the final cur of the prefixdp, we base relative calcs off this
    lowest = cur
    highest = cur
    suffixdp[-1] = (cur, cur)

    for i in reversed(range(len(suffixdp))):
        cur2 = prefixdp[i][-1]
        lowest = min(lowest, cur2)
        highest = max(highest, cur2)
        suffixdp[i] = (cur2 - lowest, highest - cur2)

    for l, r in queries:
        # all instruction between l and r inclusive are ignored
        highest, lowest, cur = prefixdp[l - 1]
        #print(l, prefixdp[l - 1], r, suffixdp[r])
        drop, rise = suffixdp[r]
        lowest = min(lowest, cur - drop)
        highest = max(highest, cur + rise)
        # distinct vals:
        # 0 to highest plus abs lowest if lowest < 0
        total = highest + 1  # to include 0
        if lowest < 0:
            total += abs(lowest)
        print(total)


def readinput():
    tc = getInt()
    for _ in range(tc):
        n, m = getInts()
        ops = getString()
        queries = []
        for _ in range(m):
            l, r = getInts()
            queries.append((l, r))
        solve(ops, queries)


readinput()
