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.*;
public class check4  {

    public static void find(int min1[],int max1[],int n,StringBuilder sb){

        min1[0]=max1[0]=0;
        int val=0, mini=0,maxi=0;

        for(int i=1;i<n+1;i++){

            if(sb.charAt(i-1)=='-'){
                val--;
            }
            else val++;

            mini=Math.min(mini,val);
            maxi=Math.max(maxi,val);

            min1[i]=val-mini;
            max1[i]=maxi-val;
        }
    }
    public static void main(String[] args) throws IOException{

        Reader sc=new Reader();
        PrintWriter out = new PrintWriter(System.out);
        int t=sc.nextInt();

        while(t-->0)
        {
            int n=sc.nextInt();
            int m=sc.nextInt();

            String s=sc.next();
            StringBuilder sb = new StringBuilder();
            sb.append(s);

            int min1[]=new int[n+2];
            int max1[]=new int[n+2];

            find(min1,max1,n,sb);
//            StringBuilder sb2=new StringBuilder();
//            sb2=sb.reverse();

            int min2[]=new int[n+2];
            int max2[]=new int[n+2];

            int arr1[]=new int[n+1];
            for(int i=1;i<n+1;i++){

                if(s.charAt(i-1)=='-'){
                    arr1[i]=arr1[i-1]-1;
                }
                else{
                    arr1[i]=arr1[i-1]+1;
                }
            }
            int arrmin[]=new int[n+1];
            arrmin[n]=arr1[n];

            int arrmax[]=new int[n+1];
            arrmax[n]=arr1[n];

            for(int i=n-1;i>=0;i--){
                arrmin[i]=Math.min(arrmin[i+1],arr1[i]);
                arrmax[i]=Math.max(arrmax[i+1],arr1[i]);
            }
            for(int i=0;i<=n;i++){
                min2[i]=arr1[i]-arrmin[i];
                max2[i]=arrmax[i]-arr1[i];
            }
//              out.println("\n min1 = "+Arrays.toString(min1)+"\n max1 = "+Arrays.toString(max1));
//            out.println("\n min2 = "+Arrays.toString(min2)+"\n max2 = "+Arrays.toString(max2));

            for(int i=0;i<m;i++){

                int i1=sc.nextInt()-1;
                int i2=sc.nextInt()-1;

                int a1[]={min1[i1],max1[i1]};
                int a2[]={min2[i2+2],max2[i2+2]};

               if(i2+1<n){
                   if(s.charAt(i2+1)=='-'){
                       a2[0]+=1;
                       if(a2[1]>0) a2[1]-=1;
                   }
                   else{
                       if(a2[0]>0) a2[0]-=1;
                       a2[1]+=1;
                   }
               }
               int ans=Math.max(a1[0],a2[0])+Math.max(a1[1],a2[1])+1;
               out.println(ans);
//                out.println(Arrays.toString(a1)+" "+Arrays.toString(a2));


            }

        }
        out.flush();
    }

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

        long ans1 = power(x,power/2);
        ans1=ans1*ans1;

        if(power%2==0) return ans1;
        return x*ans1;
    }

    //    (a*a_inverse) = 1(mod m)
//    finding a_inverse
    public static long modInverse(long a,long m)
    {
//        works only when m is prime
        long g=gcd(a,m);
        if(g==1) return power(a,m-2,m);
        else return -1;
    }

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

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

        if(power%2==0) return p;
        return (x*p)%m;
    }
    public static long gcd(long small,long large)
    {
        if(small==0) return large;
        return gcd(large % small,small);
    }

    public static boolean isprime(long no)
    {
        if(no<=1) return false;
        if(no<=3) return true;
        if(no%2==0 || no%3==0) return false;
        // 6k+1 6k+5 can be prime
        for(long i=5;i*i<=no;i+=6)
        {
            if(no%(i)==0 || no%(i+2)==0)
                return false;
        }
        return true;
    }

    //    prime no smaller than or equal to n
    public static boolean[] prime_nos_till_no(int no)
    {
        boolean prime[]=new boolean[no+1];
//        prime[i]== true means prime
//        prime[i]== false means not a prime
//        initialize prime array as true

        Arrays.fill(prime,true);
        prime[0]=false;
        for(int i=2;i*i<=no;i++)
        {
            if(prime[i]==true)
            {
                for(int j=i*i;j<=no;j+=i)
                {
                    prime[j]=false;
                }
            }
        }
        return prime;

    }
    public static void shufflearray(long arr[])
    {


        int n=arr.length;
        Random rand=new Random();
        for(int i=0;i<n;i++)
        {
            long temp=arr[i];
            int randomPos=i+rand.nextInt(n-i);
            arr[i]=arr[randomPos];
            arr[randomPos]=temp;
        }
    }
    //       Arrays.sort(arr, new Comparator<pair>() {
//        //@Override
//        public int compare(pair o1, pair o2) {
//            long l1=o1.a-o2.a;
//            if(l1<0L) return -1;
//            if(l1==0) return 0;
//            return 1;
//        }
//    });
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String nextLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() throws IOException{
            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 int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }

    }

}