题目描述

Nitori is learning postfix expressions. She has a incomplete postfix expression $E$ of length $n$. Being a Youkai, she wants to find its magical property.

Her postfix expression contains the Bitwise Or operator (denoted as |), the Bitwise And operator (denoted as &), and numbers 0 and 1. Being incomplete, some operators have not been decided yet and are denoted as ?. She promised that $E$ will become a vaild postfix expression after you complete it.

In this problem, the term substring is defined as a continuous segment of $E$. Two substrings are considered different as long as their positions or length differ. So 1?0, 01?0 are all substrings of 01?01?| , but 0101 is not.

Nitori found out that a substring of her expression is magical if and only if the following conditions are met:

• It is possible to transform it into a valid postfix expression after replacing ? with either & or | .
• Among these transformations, it is possible to find at least one of them that after applying it, the expression yields $0$, and at least one of them that after applying it, the expression yields $1$.

Your task is to find out the number of magical substrings.

输入格式

The first line contains an integer $T$, the number of test cases.

For each test case, input one integer $n$ and an expression $E$ in a single line.

输出格式

For each test case, print one integer which is the answer.

题目大意

给定一个合法的含 |&?01 的后缀表达式（以字符串形式给出，其为“合法的”代表将所有 ? 替换为运算符后其会成为一个合法的后缀表达式），试求出其有多少个子串满足：

• 将所有的 ? 替换成 | 或 & 后，该串为合法的后缀表达式；
• 存在一种将所有的 ? 替换成 | 或 & 的方法使得该式所得结果为 $0$，同时也存在替换方法使得结果为 $1$。

请输出这样的子串的数量。两个子串是不同的仅当它们长度不同或位置不同。

2
3 01?
7 01?01?|

1
3

提示

Constraints

$1\le T,n\le 2\times 10^6$. The sum of $n$ of all test cases $\le 2\times 10^6$.