说明

时间限制：1 Sec 内存限制：256 MB 输入文件：substring.in 输出文件：substring.out

如果一个非空字符串中每个字符出现的次数都不超过该字符串中不同字符的个数，我们就称这个字符串为“多样字符串”。

例如：

• 字符串 7 是多样的，因为 7 出现了 $1$ 次，而不同字符的个数也是 $1$。
• 字符串 77 不是多样的，因为 7 出现了 $2$ 次，而不同字符的个数只有 $1$。
• 字符串 1010 是多样的，因为 0 和 1 都出现了 $2$ 次，而不同字符的个数是 $2$。
• 字符串 6668 不是多样的，因为 6 出现了 $3$ 次，而不同字符的个数是 $2$。

给定一个只包含数字 0 到 9 的字符串 $s$，请你计算它的所有子串中有多少个多样字符串。

注意，如果同一个多样字符串在 $s$ 中出现多次，每次出现都要单独计数。例如，在字符串 77 中有两个多样的子串 7，所以该字符串的答案为 $2$。

注：从字符串 $s$ 的开头向后和结尾向前任意挑选连续的 $0$ 个或多个字符并删除后，留下的部分叫做 $s$ 的子串。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问；

接下来为 $t$ 组询问，每组询问包含一行，为一个只包含数字 0 到 9 的字符串 $s$。

输出格式

$t$ 行，第 $i$ 行为一个整数，表示对第 $i$ 组询问的回答。

样例

样例 1

7
7
77
1010
01100
399996
23456
789987887987998798

1
2
10
12
10
15
106

样例说明：

第 $3$ 组询问中，多样字符串有 0（出现 $2$ 次）、01、010、1（出现 $2$ 次）、10（出现 $2$ 次）、101、1010；

第 $4$ 组询问中，多样字符串有 0（出现 $3$ 次）、01、011、01、0110、1（出现 $2$ 次）、10、100、110、1100；

第 $5$ 组询问中，多样字符串有 3、39、6、9（出现 $4$ 次）、399、996、96；

第 $6$ 组询问中，字符串 23456 的所有 $15$ 个非空子串都是多样的；

数据范围

$1 \le t \le 10^4$

令 $|s|$ 表示字符串 $s$ 的长度，有 $1 \le |s| \le 2 \times 10^5$

题目保证所有询问中的 $|s|$ 之和不超过 $2 \times 10^5$