题目描述

bjh 有一个长度为 $n$ 的只由字符 0 和 1 构成的字符串 $s$。

bjh 的每次操作可以选择一个长度大于 1 的极大的只包含一种字符的子串，将这一整个子串修改为与其中字符相反的一个字符（如 $11001$ 一次操作后可以改为 $0001$ 或 $1111$）。

bjh 会一直操作下去，直到字符串无法再被操作，请帮他找到所有操作方案中最大操作次数和最小操作次数的差值。

输入格式

本题包含多组数据。第一行输入一个整数 $T$ $(1\leq T\leq 10^4)$，表示数据组数。

对于每组数据，第一行输入一个整数 $n$ $(1\leq n\leq 10^5)$，表示字符串的长度。

第二行输入一个字符串 $s$，表示初始的字符串。

保证所有数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组数据，输出一个整数，表示最大操作次数和最小操作次数的差值。

2
5
11001
5
11000

1
0