题目描述

给定一个长度为 $n$ 的 01 串 $S$，但该字符串中有一些位置的字符是未知的，用 ? 表示。

我们需要将所有的 ? 替换为 0 或 1，使得最终的字符串 $S$ 中的逆序对数量最大。

输出最大的逆序对数量。

输入格式

第一行输入一个正整数 $t$，表示测试用例的数量。

对于每组测试数据：

第一行输入一个正整数 $n$，表示字符串的长度。

第二行输入一个长度为 $n$ 的字符串 $S$，表示给定的字符串。

$(1\le t\le 10^5,2\le n\le 2\times 10^5,S_i\in\{0,1,?\})$

保证所有测试用例的字符串长度之和不超过 $2\times 10^5$。

输出格式

对于每组测试数据，输出一行一个整数表示答案。

样例输入

4
3
110
3
1?0
4
????
7
1?0?0?1

样例输出

2
2
4
8