题目描述

现在有十二个巨人，分别用$A,B \dots L$十二个大写字符表示。

每天会有一个巨人会出现供人参观。

现在你知道了连续的巨人出现的顺序的字符串$S$.

请你找出所有满足条件的时间段：如果有一段连续的时间，使得$A,B,C$三个巨人出现的次数相同，这段连续时间就是你找到的满足条件的时间段。

你需要统计不同连续时间的个数。

输入格式

一行大写字符$A,B \dots L$组成的字符串$S$.

输出格式

一个整数ans，表示要求的不同连续时间的个数。

样例数据

input

ABADCABA

output

4

满足条件的时间段为2个：BADC ,D , CAB , DCAB

数据规模与约定

40% 数据满足 ：$|S| \leq 100$

70% 数据满足： $|S| \leq 1000$

100% 数据满足： $|S| \leq 1000000$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$