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 java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class D {
    private static FastReader fr = new FastReader();
    private static PrintWriter out=new PrintWriter(System.out);

    private static int[] dp;

    // A utility function to get the
    // middle index of given range.
    static int getMid(int s, int e)
    {
        return s + (e - s) / 2;
    }

    /*
    * A recursive function to get the sum
    of values in given range of the array.
    * The following are parameters for this function.
    *
    * st -> Pointer to segment tree
    * node -> Index of current node in
    *         the segment tree.
    * ss & se -> Starting and ending indexes
    *         of the segment represented
    *         by current node, i.e., st[node]
    * l & r -> Starting and ending indexes
    *         of range query
    */
    static int MaxUtil(int[] st, int ss, int se,
                       int l, int r, int node)
    {

        // If segment of this node is completely
        // part of given range, then return
        // the max of segment
        if (l <= ss && r >= se)
            return st[node];

        // If segment of this node does not
        // belong to given range
        if (se < l || ss > r)
            return Integer.MIN_VALUE;

        // If segment of this node is partially
        // the part of given range
        int mid = getMid(ss, se);

        return Math.max(MaxUtil(st, ss, mid, l, r, 2 * node + 1),
                MaxUtil(st, mid + 1, se, l, r, 2 * node + 2));
    }

    static int MinUtil(int[] st, int ss, int se,
                       int l, int r, int node)
    {

        // If segment of this node is completely
        // part of given range, then return
        // the max of segment
        if (l <= ss && r >= se)
            return st[node];

        // If segment of this node does not
        // belong to given range
        if (se < l || ss > r)
            return Integer.MAX_VALUE;

        // If segment of this node is partially
        // the part of given range
        int mid = getMid(ss, se);

        return Math.min(MinUtil(st, ss, mid, l, r, 2 * node + 1),
                MinUtil(st, mid + 1, se, l, r, 2 * node + 2));
    }

    /*
    * A recursive function to update the
    nodes which have the given index in their
    * range. The following are parameters
    st, ss and se are same as defined above
    * index -> index of the element to be updated.
    */
    static void updateValue(int arr[], int[] st, int ss,
                            int se, int index, int value, int node)
    {
        if (index < ss || index > se)
        {
            System.out.println("Invalid Input");
            return;
        }

        if (ss == se)
        {

            // update value in array and in segment tree
            arr[index] = value;
            st[node] = value;
        }
        else
        {
            int mid = getMid(ss, se);

            if (index >= ss && index <= mid)
                updateValue(arr, st, ss, mid, index, value, 2 * node + 1);
            else
                updateValue(arr, st, mid + 1, se, index, value, 2 * node + 2);

            st[node] = Math.max(st[2 * node + 1], st[2 * node + 2]);
        }
        return;
    }

    // Return max of elements in range from
    // index l (query start) to r (query end).
    static int getMax(int[] st, int n, int l, int r)
    {

        // Check for erroneous input values
        if (l < 0 || r > n - 1 || l > r)
        {
            System.out.printf("Invalid Input\n");
            return -1;
        }

        return MaxUtil(st, 0, n - 1, l, r, 0);
    }

    static int getMin(int[] st, int n, int l, int r)
    {

        // Check for erroneous input values
        if (l < 0 || r > n - 1 || l > r)
        {
            System.out.printf("Invalid Input\n");
            return -1;
        }

        return MinUtil(st, 0, n - 1, l, r, 0);
    }

    // A recursive function that constructs Segment
    // Tree for array[ss..se]. si is index of
    // current node in segment tree st
    static int constructMaxSTUtil(int arr[], int ss,
                               int se, int[] st, int si)
    {

        // If there is one element in array, store
        // it in current node of segment tree and return
        if (ss == se)
        {
            st[si] = arr[ss];
            return arr[ss];
        }

        // If there are more than one elements, then
        // recur for left and right subtrees and
        // store the max of values in this node
        int mid = getMid(ss, se);

        st[si] = Math.max(constructMaxSTUtil(arr, ss, mid, st, si * 2 + 1),
                constructMaxSTUtil(arr, mid + 1, se, st, si * 2 + 2));

        return st[si];
    }

    static int constructMinSTUtil(int arr[], int ss,
                                  int se, int[] st, int si)
    {

        // If there is one element in array, store
        // it in current node of segment tree and return
        if (ss == se)
        {
            st[si] = arr[ss];
            return arr[ss];
        }

        // If there are more than one elements, then
        // recur for left and right subtrees and
        // store the max of values in this node
        int mid = getMid(ss, se);

        st[si] = Math.min(constructMinSTUtil(arr, ss, mid, st, si * 2 + 1),
                constructMinSTUtil(arr, mid + 1, se, st, si * 2 + 2));

        return st[si];
    }


    /*
    * Function to construct segment tree from
    given array. This function allocates
    * memory for segment tree.
    */
    static int[] constructMaxST(int arr[], int n)
    {

        // Height of segment tree
        int x = (int) Math.ceil(Math.log(n) / Math.log(2));

        // Maximum size of segment tree
        int max_size = 2 * (int) Math.pow(2, x) - 1;

        // Allocate memory
        int[] st = new int[max_size];

        // Fill the allocated memory st
        constructMaxSTUtil(arr, 0, n - 1, st, 0);

        // Return the constructed segment tree
        return st;
    }

    static int[] constructMinST(int arr[], int n)
    {

        // Height of segment tree
        int x = (int) Math.ceil(Math.log(n) / Math.log(2));

        // Maximum size of segment tree
        int max_size = 2 * (int) Math.pow(2, x) - 1;

        // Allocate memory
        int[] st = new int[max_size];

        // Fill the allocated memory st
        constructMinSTUtil(arr, 0, n - 1, st, 0);

        // Return the constructed segment tree
        return st;
    }

    private static int min(int x, int y, int[] st, int n){
        if(y < 0) return 0;
        if(x >= n) return 0;
        return getMin(st, n, x, y);
    }

    private static int max(int x, int y, int[] st, int n){
        if(y < 0) return 0;
        if(x >= n) return 0;
        return getMax(st, n, x, y);
    }

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        // code goes here
        int t = fr.nextInt();
        while (t-- > 0){
            int n = fr.nextInt();
            int m = fr.nextInt();
            String s = fr.next();
            int[] arr = new int[n];
            int current = 0;
            for(int i = 0; i < n; i++){
                if(s.charAt(i) == '+'){
                    current++;
                } else {
                    current--;
                }
                arr[i] = current;
            }
            int[] maxSt = constructMaxST(arr, n);
            int[] minSt = constructMinST(arr, n);
            for(int i = 0; i < m; i++){
                int l = fr.nextInt() - 1;
                int r = fr.nextInt() - 1;
                // use segment tree to get this or range min query.
                int min1 = min(0, l - 1, minSt, n);
                int max1 = max(0, l - 1, maxSt, n);
                max1 = Math.max(max1, 0);
                min1 = Math.min(min1, 0);
                int min2 = min(r + 1, n - 1, minSt, n);
                if(r < n - 1){
                    min2 -= arr[r] - ((l - 1 >= 0 ? arr[l - 1] : 0));
                }
                int max2 = max(r + 1, n - 1, maxSt, n);
                if(r < n - 1){
                    max2 -= arr[r] - ((l - 1 >= 0 ? arr[l - 1] : 0));
                }

                if(max1 < min2 || max2 < min1){
                    sb.append((max1 - min1 + 1) + (max2 - min2 + 1)).append("\n");
                } else if(min1 <= min2 && max1 >= max2){
                    sb.append((max1 - min1 + 1)).append("\n");
                } else if(min2 <= min1 && max2 >= max1){
                    sb.append((max2 - min2 + 1)).append("\n");
                } else {
                    int min = Math.min(min1, min2);
                    int max = Math.max(max1, max2);
                    sb.append((max - min + 1)).append("\n");
                }
            }
        }
        System.out.print(sb.toString());
    }

    static class FastReader{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");

        public String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public int[] nextIntArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public long[] nextLongArray(int n) {
            long[] a=new long[n];
            for (int i=0; i<n; i++) a[i]=nextLong();
            return a;
        }
    }

    static class Pair<A, B>{
        A first;
        B second;
        public Pair(A first, B second){
            this.first = first;
            this.second = second;
        }
    }

    static long mod(String num, long a)
    {
        // Initialize result
        long res = 0;

        // One by one process all digits of 'num'
        for (int i = 0; i < num.length(); i++)
            res = (res*10 +  num.charAt(i) - '0') %a;

        return res;
    }

    static long binomialCoeff(long n, long k, long MOD)
    {
        long res = 1;

        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;

        // Calculate value of
        // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
        for (int i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
            res %= MOD;
        }

        return res;
    }

    static long power(long x, long y, long p)
    {

        // Initialize result
        long res = 1;

        // Update x if it is more than or
        // equal to p
        x = x % p;

        while (y > 0) {

            // If y is odd, multiply x
            // with result
            if (y % 2 == 1)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }

        return res;
    }

    // Returns n^(-1) mod p
    static long modInverse(long n, long p)
    {
        return power(n, p - 2, p);
    }

    // Returns nCr % p using Fermat's
    // little theorem.
    static long nCrModPFermat(int n, int r,
                              long p)
    {

        // Base case
        if (r == 0)
            return 1;

        // Fill factorial array so that we
        // can find all factorial of r, n
        // and n-r
        long[] fac = new long[n + 1];
        fac[0] = 1;

        for (int i = 1; i <= n; i++)
            fac[i] = fac[i - 1] * i % p;

        return (fac[n] * modInverse(fac[r], p)
                % p * modInverse(fac[n - r], p)
                % p)
                % p;
    }
}
