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.*;
import java.util.*;
import java.math.*;
import java.lang.*;

public class Main implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(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 String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        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 long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long 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 double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    public static void main(String args[]) throws Exception {
        new Thread(null, new Main(), "Main", 1 << 27).start();
    }

    static class Pair {
        int f;
        int s;
        int p;
        PrintWriter w;

        // int t;

        Pair(int f, int s) {
            // Pair(int f,int s, PrintWriter w){
            this.f = f;
            this.s = s;
            // this.p = p;
            // this.w = w;
            // this.t = t;

        }

        public static Comparator<Pair> wc = new Comparator<Pair>() {
            public int compare(Pair e1, Pair e2) {

                // 1 for swap
                if (Math.abs(e1.f) - Math.abs(e2.f) != 0) {
                    // e1.w.println("**"+e1.f+" "+e2.f);
                    return (Math.abs(e1.f) - Math.abs(e2.f));
                } else {
                    // e1.w.println("##"+e1.f+" "+e2.f);
                    return (Math.abs(e1.s) - Math.abs(e2.s));
                }

            }
        };
    }

    public static ArrayList<Integer> sieve(int N) {
        int i, j, flag;

        ArrayList<Integer> p = new ArrayList<Integer>();

        for (i = 1; i < N; i++) {

            if (i == 1 || i == 0)
                continue;

            flag = 1;

            for (j = 2; j <= i / 2; ++j) {
                if (i % j == 0) {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) {
                p.add(i);
            }
        }
        return p;
    }

    public static long gcd(long a, long b) {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    //// recursive dfs
    public static int dfs(int s, ArrayList<Integer>[] g, long[] dist, boolean[] v, PrintWriter w, int p) {
        v[s] = true;
        int ans = 1;
        // int n = dist.length - 1;
        int t = g[s].size();
        // int max = 1;
        for (int i = 0; i < t; i++) {
            int x = g[s].get(i);
            if (!v[x]) {
                // dist[x] = dist[s] + 1;
                ans = Math.min(ans, dfs(x, g, dist, v, w, s));
            } else if (x != p) {
                // w.println("* " + s + " " + x + " " + p);
                ans = 0;
            }
        }
        // max = Math.max(max,(n-p));
        return ans;
    }

    //// iterative BFS
    public static int bfs(int s, ArrayList<Integer>[] g, long[] dist, boolean[] b, PrintWriter w, int p) {
        b[s] = true;
        int siz = 1;
        // dist--;
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        while (q.size() != 0) {
            int i = q.poll();
            Iterator<Integer> it = g[i].listIterator();
            int z = 0;
            while (it.hasNext()) {
                z = it.next();
                if (!b[z]) {
                    b[z] = true;
                    // dist--;
                    dist[z] = dist[i] + 1;
                    // siz++;
                    q.add(z);
                } else if (z != p) {
                    siz = 0;
                }
            }

        }
        return siz;
    }

    public static int lower(int key, int[] a) {
        int l = 0;
        int r = a.length - 1;
        int res = 0;

        while (l <= r) {
            int mid = (l + r) / 2;

            if (a[mid] <= key) {
                l = mid + 1;
                res = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return res;
    }

    public static long power(long x, long y, long m) {
        if (y == 0)
            return 1;

        long p = power(x, y / 2, m) % m;
        p = (p * p) % m;

        if (y % 2 == 0)
            return p;
        else
            return (x * p) % m;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////////////
    // code here
    int[] parent;
    int[] dist;
    int[] height;
    boolean[] vis;
    HashSet<Integer>[] g;
    int[] col;

    public void run() {

        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
        int defaultValue = 0;
        int mod = 1000000007;
        int oo = (int) 1e9;

        int test = 1;
        test = sc.nextInt();
        while (test-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            char[] a = sc.next().toCharArray();
            int[][] pre = new int[2][n + 2];
            int[][] suf = new int[2][n + 2];
            int[] cur = new int[n + 2];

            for (int i = 1; i <= n; i++) {
                if (a[i - 1] == '+')
                    cur[i] = cur[i - 1] + 1;
                else
                    cur[i] = cur[i - 1] - 1;

                if (cur[i] > pre[0][i - 1]) {
                    pre[0][i] = cur[i];
                    pre[1][i] = pre[1][i - 1];
                } else if (cur[i] < pre[1][i - 1]) {
                    pre[0][i] = pre[0][i - 1];
                    pre[1][i] = cur[i];
                } else {
                    pre[0][i] = pre[0][i - 1];
                    pre[1][i] = pre[1][i - 1];
                }
            }

            for (int i = n; i > 0; i--) {
                if (a[i - 1] == '+') {
                    suf[0][i] = suf[0][i + 1] + 1;
                    if (suf[1][i + 1] != 0)
                        suf[1][i] = suf[1][i + 1] + 1;
                } else {
                    suf[1][i] = suf[1][i + 1] - 1;
                    if (suf[0][i + 1] != 0)
                        suf[0][i] = suf[0][i + 1] - 1;
                }

            }

            for (int i = 0; i < m; i++) {
                int ans = 1;
                int l = sc.nextInt();
                int r = sc.nextInt();
                ans += (pre[0][l - 1] - pre[1][l - 1]);
                // w.println("*" + ans);
                if (suf[0][r + 1] > 0)
                    ans += Math.max((cur[l - 1] + suf[0][r + 1]) - pre[0][l - 1], 0);
                // w.println("**" + ans);
                if (suf[1][r + 1] < 0)
                    ans += -1 * Math.min((cur[l - 1] + suf[1][r + 1]) - pre[1][l - 1], 0);
                // w.println("***" + ans);
                // w.println(cur[l - 1] + " " + pre[0][l - 1] + " " + pre[1][l - 1] + " " +
                // suf[0][r + 1] + " "
                // + suf[1][r + 1]);
                w.println(ans);
            }

        }

        w.flush();
        w.close();

    }

}
