Description

妮特莉正在学习后缀表达式。她有一个长度为 $n$ 的不完整后缀表达式 $E$。作为妖怪，她想要找到它的魔法属性。

她的后缀表达式包含按位或运算符（记作 |）、按位与运算符（记作 &），以及数字 0 和 1。由于不完整，一些运算符尚未决定，用 ? 表示。她保证 $E$ 在你完成它之后将成为一个有效的后缀表达式。

在这个问题中，术语子串定义为 $E$ 的一个连续片段。**只要位置或长度不同，两个子串就被认为是不同的。**所以 1?0，01?0 都是 01?01?| 的子串，但 0101 不是。

妮特莉发现她的表达式的一个子串是魔法的，当且仅当满足以下条件：

• 在将 ? 替换为 & 或 | 后，可以将其转换为一个有效的后缀表达式。
• 在这些转换中，至少能找到一种转换，使得应用后表达式的结果为 $0$，并且至少能找到一种转换，使得应用后表达式的结果为 $1$。

你的任务是找出魔法的子串的数量。

Input Format

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例，在一行中输入一个整数 $n$ 和一个表达式 $E$。

Output Format

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

2
3 01?
7 01?01?|

1
3

Hint

约束条件

$1\le T,n\le 2\times 10^6$。所有测试用例的 $n$ 之和 $\le 2\times 10^6$。

题面翻译由 ChatGPT-4o 提供。