P7941 「Wdcfr-1」Magical Expression

妮特莉正在学习后缀表达式。她有一个长度为 $n$ 的不完整后缀表达式 $E$。作为妖怪，她想要找到它的魔法属性。 她的后缀表达式包含按位或运算符（记作 `|`）、按位与运算符（记作 `&`），以及数字 `0` 和 `1`。由于不完整，一些运算符尚未决定，用 `?` 表示。她保证 $E$ **在你完成它之后将成为一个*有效*的后缀表达式**。 在这个问题中，术语*子串*定义为 $E$ 的一个连续片段。**只要位置或长度不同，两个子串就被认为是不同的。**所以 `1?0`，`01?0` 都是 `01?01?|` 的子串，但 `0101` 不是。 妮特莉发现她的表达式的一个子串是*魔法的*，当且仅当满足以下条件： - 在将 `?` 替换为 `&` 或 `|` 后，可以将其转换为一个*有效*的后缀表达式。 - 在这些转换中，至少能找到一种转换，使得应用后表达式的结果为 $0$，并且至少能找到一种转换，使得应用后表达式的结果为 $1$。 你的任务是找出*魔法的*子串的数量。

第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例，在一行中输入一个整数 $n$ 和一个表达式 $E$。

对于每个测试用例，输出一个整数，表示答案。

### 约束条件 $1\le T,n\le 2\times 10^6$。所有测试用例的 $n$ 之和 $\le 2\times 10^6$。 题面翻译由 ChatGPT-4o 提供。