给定一个长度为n的01串s。你可以按下面方法对s进行操作。

• 1. 选择一个位置i（其中i取值为1至字符串s的长度）,删除串第i个字符。
• 2. 若串不空，把01串前面连续的一串1或者是一串0删除。

请注意，每次操作上面的两步都要做。
如s=111010,第一次操作为下面6种操作中的一种：

• 1.选择i=1: 得到111010 → 11010 → 010;
• 2.选择i=2: 得到111010 → 11010 → 010;
• 3.选择i=3: 得到111010 → 11010 → 010;
• 4.选择i=4: 得到111010 → 11110 → 0;
• 5.选择i=5: 得到111010 → 11100 → 00;
• 6.选择i=6: 得到111010 → 11101 → 01.

请问按上面方法操作，最多经过多少次操作后字符串s变为空串

第一行仅包含一个整数t (1≤t≤1000),表示测试样例的数量
每组测试样例的第一行为n(1≤n≤2e5),表示字符串的长度。第二行为长度为n的01串。
测试样例保证所有的n之和不超过2e5

对每一组测试，输出一个整数，即最多的操作次数。

5
6
111010
1
0
1
1
2
11
6
101010

3
1
1
1
3

第一组测试样例中，可以这样操作，选择i=2,删除操作后得到010，接着选择i=3，删除操作后得到1，最后，选择i=1得到空串。