该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

定义一个字符串为 好字符串 当且仅当：字符串中 同时存在数字 $1,2, \cdots ,9$ 且这九种数字的出现次数都相等（出现次数均为正整数）。

现在给定一个仅由字符 1 到 9 组成的长度为 $n$ 的字符串，请计算该字符串中有多少个 子串 是好字符串。

输入格式

输入包含多组测试数据：

• 第一行包含一个整数 $t$（$1\le t\le 10^3$），表示测试数据组数。

• 接下来 $t$ 组数据，每组包含两行：

  • 第一行包含一个整数 $n$（$1\le n\le 3 \times 10^4$），表示字符串长度；
  • 第二行包含长度为 $n$ 的字符串，且字符串仅由字符 '1' 到 '9' 构成。

保证 $t$ 组测试数据中 $n$ 的总和不超过数据范围对应的限制。

输出格式

对于每组测试数据，输出一行，包含一个整数 —— 给定字符串中为好字符串的子串个数。

样例输入

2
9
123456789
10
1122334455

样例输出

1
0

说明

数据范围