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. 
/*
 * Date Created : 15/1/2021
 * Have A Good Day !
 */

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Arpit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        DProgram solver = new DProgram();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }
    
    static class DProgram {
        public void solve(int testNumber, FastReader r, OutputWriter out) {
            int n = r.nextInt(), m = r.nextInt();
            char[] s = r.next().toCharArray();
            int[] x = new int[n + 1];
            int co_ord = 0;
            for (int i = 1; i <= n; i++) {
                if (s[i - 1] == '-') co_ord--;
                else co_ord++;
                x[i] = co_ord;
            }
            int[] prefix_max = new int[n + 2], prefix_min = new int[n + 2];
            int[] suffix_max = new int[n + 2], suffix_min = new int[n + 2];
            prefix_min[0] = 0;
            prefix_max[0] = 0;
            prefix_min[n + 1] = 0;
            prefix_max[n + 1] = 0;
//        prefix_min[1] = x[1];
//        prefix_max[1] = x[1];
            for (int i = 1; i <= n; i++) {
                prefix_max[i] = Math.max(x[i], prefix_max[i - 1]);
                prefix_min[i] = Math.min(x[i], prefix_min[i - 1]);
            }
            suffix_min[n + 1] = 0;
            suffix_max[n + 1] = 0;
            suffix_min[0] = 0;
            suffix_max[0] = 0;
//        suffix_min[n] = x[n];
//        suffix_max[n] = x[n];
            for (int i = n; i >= 1; i--) {
                if (i == n) {
                    suffix_min[i] = x[n];
                    suffix_max[i] = x[i];
                } else {
                    suffix_min[i] = Math.min(x[i], suffix_min[i + 1]);
                    suffix_max[i] = Math.max(x[i], suffix_max[i + 1]);
                }
            }
//        out.println("----");
//        out.debugln("x", x);
//        out.debugln("prefix_min", prefix_min);
//        out.debugln("prefix_max", prefix_max);
//        out.debugln("suffix_min", suffix_min);
//        out.debugln("suffix_max", suffix_max);
//        out.println("----");
            for (int i = 1; i <= m; i++) {
                int lt = r.nextInt(), rt = r.nextInt();
                int pre_min = prefix_min[lt - 1], suff_min = suffix_min[rt + 1];
                int pre_max = prefix_max[lt - 1], suff_max = suffix_max[rt + 1];
                int prev = x[lt - 1], check = rt != n ? x[rt] : 0;
                int min = Math.min(pre_min, prev + (suff_min - check));
                min = Math.min(min, prev);
                int max = Math.max(pre_max, prev + (suff_max - check));
                max = Math.max(max, prev);
//            out.debugln("pre_min", pre_min);
//            out.debugln("suff_min", suff_min);
//            out.debugln("pre_max", pre_max);
//            out.debugln("suff_max", suff_max);
//            out.debugln("prev", prev);
//            out.debugln("min", min);
//            out.debugln("max", max);
                out.println((max - min + 1));
//            out.println("----");
            }
        }
        
    }
    
    static class OutputWriter {
        private final PrintWriter writer;
        
        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }
        
        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }
        
        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                writer.print(objects[i]);
                if (i != objects.length - 1) writer.print(" ");
            }
        }
        
        public void println(Object... objects) {
            print(objects);
            writer.println();
        }
        
        public void close() {
            writer.close();
        }
        
    }
    
    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;
        
        public FastReader(InputStream stream) {
            this.stream = stream;
        }
        
        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }
        
        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        
        public String nextString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        
        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }
        
        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        public String next() {
            return nextString();
        }
        
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
            
        }
        
    }
}

