You have a string s consisting of n characters. Each character is either 0 or 1.

You can perform operations on the string. Each operation consists of two steps:

  1. select an integer i from 1 to the length of the string s, then delete the character s_i (the string length gets reduced by 1, the indices of characters to the right of the deleted one also get reduced by 1); 
  2. if the string s is not empty, delete the maximum length prefix consisting of the same characters (the indices of the remaining characters and the string length get reduced by the length of the deleted prefix). 



Note that both steps are mandatory in each operation, and their order cannot be changed.

For example, if you have a string s = 111010, the first operation can be one of the following:

  1. select i = 1: we'll get 111010 → 11010 → 010; 
  2. select i = 2: we'll get 111010 → 11010 → 010; 
  3. select i = 3: we'll get 111010 → 11010 → 010; 
  4. select i = 4: we'll get 111010 → 11110 → 0; 
  5. select i = 5: we'll get 111010 → 11100 → 00; 
  6. select i = 6: we'll get 111010 → 11101 → 01. 



You finish performing operations when the string s becomes empty. What is the maximum number of operations you can perform?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the string s.

The second line contains string s of n characters. Each character is either 0 or 1.

It's guaranteed that the total sum of n over test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print a single integer — the maximum number of operations you can perform.

Example

Input


5
6
111010
1
0
1
1
2
11
6
101010


Output


3
1
1
1
3

Note

In the first test case, you can, for example, select i = 2 and get string 010 after the first operation. After that, you can select i = 3 and get string 1. Finally, you can only select i = 1 and get empty string.

import java.io.*;
import java.util.*;


public class D1430 implements Runnable {
    public InputReader in;
    public PrintWriter out;

    public void solve() throws Exception {

        // solution goes here
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int n = in.nextInt();
            String str = in.nextLine();
            if (n == 1) {
                out.println(1);
                continue;
            }
            List<Integer> intervals = new ArrayList<>();
            int start = 0;
            for (int i = 1; i <= n; i++) {
                if (i == n || str.charAt(start) != str.charAt(i)) {
                    intervals.add(i-start);
                    start = i;
                }
            }
            int[] nums = new int[intervals.size()];
            for (int i = 0; i < nums.length; i++) {
                nums[i] = intervals.get(i);
            }
            n = nums.length;
            int res = 0;
            int p1 = 0;
            int p2 = 0;
            while (p1 < n || p2 < n) {
                while (p1 < n && nums[p1] == 1) {
                    p1++;
                }
                res++;
                if (p1 == n) {
                    p2++;
                } else {
                    nums[p1]--;
                }
                p2++;
                p1 = max(p1, p2);
            }

            out.println(res);
        }
    }

    public void run() {
        try {
            in = new InputReader(System.in);
            out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
            Locale.setDefault(Locale.US);
            int tests = 1;
            while (tests-- > 0) {
                solve();
            }
            out.close();
        } catch (Throwable e) {
            e.printStackTrace();
            System.exit(7);
        }
    }

    static int abs(int x) {
        return x < 0 ? -x : x;
    }

    static int max(int a, int b) {
        return a > b ? a : b;
    }

    static int min(int a, int b) {
        return a < b ? a : b;
    }

    static long abs(long x) {
        return x < 0 ? -x : x;
    }

    static long max(long a, long b) {
        return a > b ? a : b;
    }

    static long min(long a, long b) {
        return a < b ? a : b;
    }

    public static void main(String[] args) {
        new Thread(null, new D1430(), "tt.Main", 1 << 28).start();
    }

    static boolean OJ = System.getProperty("ONLINE_JUDGE") != null;

    public void console(Object... objects) {
        if (!OJ) {
            out.println(Arrays.deepToString(objects));
            out.flush();
        }
    }

    @SuppressWarnings({"Duplicates", "unused"})
    static class InputReader {

        private InputStream stream;
        private byte[] buf = new byte[2048];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader() {
            this.stream = System.in;
        }

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public InputReader(SpaceCharFilter filter) {
            this.stream = System.in;
            this.filter = filter;
        }

        public InputReader(InputStream stream, SpaceCharFilter filter) {
            this.stream = stream;
            this.filter = filter;
        }

        public int read() {
            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 char nextChar() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            return (char) c;
        }

        public int nextDigit() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            return c - '0';
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            boolean negative = false;
            if (c == '-') {
                negative = true;
                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 negative ? -res : res;
        }

        public int[] nextInts(int N) {
            int[] nums = new int[N];
            for (int i = 0; i < N; i++)
                nums[i] = nextInt();
            return nums;
        }

        public long[] nextLongs(int N) {
            long[] nums = new long[N];
            for (int i = 0; i < N; i++)
                nums[i] = nextLong();
            return nums;
        }

        public int nextUnsignedInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res;
        }

        public final long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            boolean negative = false;
            if (c == '-') {
                negative = true;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return negative ? -res : res;
        }

        public final long nextUnsignedLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            long 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 (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1 || c == '.'));

            if (c != '.') {
                return res * sgn;
            }
            c = read();

            long aft = 0;
            int len = 1;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                aft *= 10;
                len *= 10;
                aft += c - '0';
                c = read();
            } while (!isSpaceChar(c));

            return res * sgn + aft / (1.0 * len);
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndChar(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 boolean isEndChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            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 char[] nextChars() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            char[] chars = new char[res.length()];
            res.getChars(0, chars.length, chars, 0);
            return chars;
        }

        public int[][] nextIntMatrix(int rows, int cols) {
            int[][] matrix = new int[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        public long[][] nextLongMatrix(int rows, int cols) {
            long[][] matrix = new long[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextLong();
            return matrix;
        }

        public char[][] nextCharMap(int rows, int cols) {
            char[][] matrix = new char[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextChar();
            return matrix;
        }

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

}
