题目描述

给定一个 $01$ 字符串 $S$，有两个操作：

• 第一个操作将子串 $01$ 用 $1$ 替换；
• 第二个操作将子串 $10$ 用 $0$ 替换。

求给定字符串 $S$ 的所有子串中，有多少个子串满足经过若干次操作后，可将该子串长度变为 $1$。

本题数据量较大，建议采用较快的输入输出方式。

输入格式

第一行一个数字 $t$，表示测试数据组数。

第二行开始，上一行一个数字 $n$，表示字符串长度，下一行一个字符串。

$1≤t≤100$，$1≤n≤200000$。

输出格式

每一组测试数据输出一行，表示满足子串长度的个数。

3
2
01
3
100
4
1001

3
4
8