该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个长度为 $n$ 的整数序列 $a_1, a_2, · · · , a_n$，序列中的整数只有 $0$ 和 $1$，但序列中有些位置上的元素还没 有被确定。 现在你想往序列中未被确定的位置填入 $0$ 或者 $1$，使得其逆序对数最大。 一个序列 $a_1, a_2, · · · , a_n$ 的逆序对数定义为，满足 $1 ≤ i < j ≤ n$ 并且 $a_i > a_j$ 的整数数对 $i, j$ 的个数。

输入格式

第一行一个正整数 $T (1 ≤ T ≤ 10^4 )$，表示数据组数。

对于每组数据，第一行一个整数 $n (2 ≤ n ≤ 10^6 )$，表示序列长度。

第二行一个长度为 $n$ 仅由 $0, 1, ?$ 构成的字符串 $s$ 表示序列，其中第 $i$ 个字符 $s_i$ 为 $?$ 表示序列中 $a_i$ 未知待填充，否则表示 $a_i。$ 保证单个测试点内每组数据中 $n$ 的和不超过 $2 × 10^6。$

输出格式

对于每组数据，一行一个整数，表示最大的逆序对数。

输入样例:

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

输出样例：

2
2
4
8

Note

对于第一组样例，$110$ 的逆序对数为 $2。$

对于第二组样例，可以填充为 $100$ 或 $110$，逆序对数均为 $2。$

对于第三组样例，可以填充为 $1100$，逆序对数为 $4。$

对于第四组样例，可以填充为 $1100001$ 或 $1101001$，逆序对数均为 $8。$