这是本题的困难版本。简单版本和困难版本的唯一区别在于所求内容。

Yuki 是一个文学家！

她定义一个仅包含小写字母的字符串是 lovely 的，当且仅当：

• 该字符串中出现正奇数次的字符的数量为偶数。
• 该字符串中出现正偶数次的字符的数量为奇数。

例如，$\texttt{lovely}$ 和 $\texttt{milmon}$ 是 lovely 的，而 $\texttt{dxqwq}$ 和 $\texttt{cocoly}$ 不是 lovely 的。

现在，Yuki 有一个长度为 $n$ 的仅包含小写字母的字符串 $s$。你需要帮助她求出，有多少个数对 $(l,r)$ 满足：

• $1 \le l \le r \le n$。
• $s_l\dots s_r$ 组成的子串是 lovely 的。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $t\ (1 \le t \le 10^5)$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个正整数 $n\ (1 \le n \le 5\cdot10^5)$。
• 第二行包含一个长度为 $n$ 的字符串 $s$。

保证字符串 $s$ 中仅包含小写字母，保证所有测试数据中 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示满足条件的数对 $(l,r)$ 的数量。

样例输入

8
5
hello
6
lovely
6
milmon
5
dxqwq
6
cocoly
6
qingyu
9
coffeezzz
6
byebye

样例输出

3
1
2
1
1
0
10
4

样例解释

对于第 $1$ 组测试数据：

• $\texttt{ll}$ 中出现正奇数次的字符的数量为 $0$，出现正偶数次的字符的数量为 $1$，因此 $\texttt{ll}$ 是 lovely 的，$(3,4)$ 是满足条件的数对。
• $\texttt{hell}$ 中出现正奇数次的字符的数量为 $2$，出现正偶数次的字符的数量为 $1$，因此 $\texttt{hell}$ 是 lovely 的，$(1,4)$ 是满足条件的数对。
• $\texttt{ello}$ 中出现正奇数次的字符的数量为 $2$，出现正偶数次的字符的数量为 $1$，因此 $\texttt{ello}$ 是 lovely 的，$(2,5)$ 是满足条件的数对。
• 可以证明不存在其他满足条件的数对，因此答案为 $3$。

对于第 $2$ 组测试数据：

• $\texttt{lovely}$ 中出现正奇数次的字符的数量为 $2$，出现正偶数次的字符的数量为 $4$，因此 $\texttt{lovely}$ 是 lovely 的，$(1,6)$ 是满足条件的数对。
• 可以证明不存在其他满足条件的数对，因此答案为 $1$。