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

public class  B{

    static BufferedReader br;
    static  long mod  = 1000000000+7;
    static HashSet<Integer> p  = new HashSet<>();
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        int tc = 1;
        tc = cinI();
        long mod  = (long) (1e9+7);
        while (tc-- > 0) {
             int[] nk =readArray(2,0,0);
             int n = nk[0];//n=8 k =5 diff 3  //
             int k = nk[1];
             char[] a  = cin().toCharArray();

             int[][] pre = new int[n][2];
             int[][] suff =new int[n][2];
             // l r
            int[] sum = new int[n];
            sum[0]=a[0]=='-'?-1:1;
            pre[0][0]=Math.min(0,sum[0]);
            pre[0][1]=max(0,sum[0]);
             for(int i = 1; i<pre.length;i++ ){

                 sum[i]=sum[i-1]+(a[i]=='-'?-1:1);
                 if(sum[i]<pre[i-1][0]){
                     pre[i][0]=sum[i];

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

             }
             int s = a[n-1]=='-'?-1:1;
            StringBuilder e = new StringBuilder();
            StringBuilder p = new StringBuilder();
            // s = a[n-1]=='-'?-1:1;
             suff[n-1][0]=min(0,s);
             suff[n-1][1]=max(0,s);

            e.append(suff[n-1][0]+" ");
            p.append(suff[n-1][1]+" ");
             for(int j=n-2;j>=0;j--){
                int r = a[j]=='-'?-1:1;
                suff[j][0]=min(suff[j+1][0]+r,0);

                suff[j][1]=max(suff[j+1][1]+r,0);
             }
             StringBuilder o =new StringBuilder();
             for(int i=0;i<k;i++){
                 int[] lr = readArray(2,0,0);
                 int l  =lr[0]-1;
                 int r=lr[1]-1;
                 //0- 4  ||  2 5 || 6 8
                int curr= 0;
                int cl = 0;
                int cr = 0;
                if(l-1!=-1){
                    cl = min(cl,pre[l-1][0]);
                    cr = max(cr,pre[l-1][1]);
                    curr = sum[l-1];
                }
                // System.out.println(cl +" cc "+cr);
                int ccl  =r+1;
                int ccr = a.length-1;
                if(ccl!=a.length){
                    int min = min(0,suff[ccl][0]);
                    int max = max(0,suff[ccl][1]);
                    cl  = min(cl,curr-Math.abs(min));
                    cr  = max(cr,curr+max);
             //       System.out.println(suff[ccl][0]+" xx  "+suff[ccl][1]);
                }
                int ans = cr-cl+1;
                 System.out.println(ans);




             }
            System.out.println(o.toString());


                 }
             }




























    private static long calP(HashMap<Integer, HashSet<Integer>> graph, boolean[] vis, Stack<Integer> list,
                             long[] cost, long[] dp) {
        int par = list.pop();
        HashSet<Integer> childs = graph.get(par);
        if(childs.size()==0){
            dp[par]=0;
            return dp[par];
        }
        vis[par]=true;
        for(int c: childs){
            if(vis[c]==false){
                list.add(c);
                calP(graph, vis, list, cost, dp);
            }
            if(cost[par]>cost[c]){
                dp[par]=max(dp[par], dp[c]+cost[par]-cost[c]);
            }

        }
        return dp[par];
    }

    public static int max(int[] max) {
        int maxS=0;
        int currSum=0;
        for(int i=0;i<max.length;i++){
            currSum= currSum+max[i];
            maxS=Math.max(maxS,currSum);
        }
        // System.out.println(maxS);
        return maxS;
    }

    private static int dfs(TreeMap<Integer, HashSet<Integer>> graph, boolean[] vis, Integer key, Stack<Integer> st) {
        if(st.size()==0){
            return 0;
        }
        int par= st.pop();

        HashSet<Integer> child = graph.get(par);
        vis[par]=true;
        int nodes=1;
        for(int c:child){
            if(vis[c]==false){
                st.add(c);
                nodes+=dfs(graph,vis,c,st);
            }
        }
        return nodes;
    }


    public static boolean isSorted(int[] arr){

        for(int i=0;i<arr.length-1;i++){
            if(arr[i]>arr[i+1]){
                return false;
            }
        }
        return true;
    }



    private static long gcd(long a, long b) {
        if (a == 0)
            return b;
        if (b == 0)
            return a;

        // base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a%b, b);
        return gcd(a, b%a);
    }


    public static long min(long a,long b) {
        return Math.min(a,b);
    }
    public static int min(int a,int b) {
        return Math.min(a,b);
    }
























    public static void sieve(){
        int[] pf = new int[100000000+1];
        //0 prime //1 not prime
        pf[0]=1;
        pf[1]=1;
        for(int j=2;j<=10000;j++){

            if(pf[j]==0 ){
                p.add(j);
                for(int k=j*j;k<pf.length;k+=j){
                    pf[k]=1;
                }
            }
        }

    }






    public  static  int[] readArray(int n,int x ,int z)throws Exception{
        int[] arr= new int[n];
        String[] ar= cinA();
        for(int i =x ;i<n+x;i++){
            arr[i]=getI(ar[i-x]);
        }
        return arr;
    }
    public  static  long[] readArray(int n,int x )throws Exception{
        long[] arr= new long[n+x];
        String[] ar= cinA();
        for(int i =x ;i<n+x;i++){
            arr[i]=getL(ar[i-x]);
        }
        return arr;
    }

    public static void arrinit(String[] a,long[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Long.parseLong(a[i]);
        }
    }
    public  static HashSet<Integer>[]  Graph(int n,int edge,int directed)throws Exception{
        HashSet<Integer>[] tree=  new HashSet[n];

        for(int j=0;j<edge;j++){

            String[] uv = cinA();
            int u = getI(uv[0]);
            int v = getI(uv[1]);
            if(directed==0){

                tree[v].add(u);
            }
            tree[u].add(v);
        }
        return tree;
    }
    public static void arrinit(String[] a,int[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Integer.parseInt(a[i]);
        }
    }


    static double findRoots(int a, int b, int c) {
        // If a is 0, then equation is not
        //quadratic, but linear


        int d = b * b - 4 * a * c;
        double sqrt_val = Math.sqrt(Math.abs(d));


        // System.out.println("Roots are real and different \n");

        return Math.max((double) (-b + sqrt_val) / (2 * a),
                (double) (-b - sqrt_val) / (2 * a));


    }

    public static String cin() throws Exception {
        return br.readLine();
    }

    public static String[] cinA() throws Exception {
        return br.readLine().split(" ");
    }
    public static String[] cinA(int x) throws Exception{
        return br.readLine().split("");
    }

    public static String ToString(Long x) {
        return Long.toBinaryString(x);
    }

    public static void cout(String s) {
        System.out.println(s);
    }

    public static Integer cinI() throws Exception {
        return Integer.parseInt(br.readLine());
    }

    public static int getI(String s) throws Exception {
        return Integer.parseInt(s);
    }

    public static long getL(String s) throws Exception {
        return Long.parseLong(s);
    }

    public static long max(long a, long b) {
        return Math.max(a, b);
    }
    public static int max(int a, int b) {
        return Math.max(a, b);
    }

    public static void coutI(int x) {
        System.out.println(String.valueOf(x));
    }

    public static void coutI(long x) {
        System.out.println(String.valueOf(x));
    }

    public static Long cinL() throws Exception {
        return Long.parseLong(br.readLine());
    }

    public static void arrInit(String[] arr, int[] arr1) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = getI(arr[i]);
        }

    }
}
