Farmer John 的联合奶牛队（UCFJ）正在参加年度蹄球锦标赛！UCFJ 的 $N$ 头奶牛（$1 \le N \le 7500$）在蹄球比赛中赢得了金牌，险胜 Farmer Nhoj 的队伍。

奶牛们已经排好队准备参加颁奖典礼。她们希望 FJ 为队列中的每一个连续子序列各拍一张集体照，总共要拍 $\frac{N(N+1)}{2}$ 张照片。

然而，作为教练的 FJ 对奶牛的排列方式非常讲究。具体来说，除非子序列构成一个回文串，否则他拒绝为其拍照。这意味着对于子序列长度范围内的所有正整数 $i$，从左端数第 $i$ 头奶牛的品种必须与从右端数第 $i$ 头奶牛的品种相同。每头奶牛的品种要么是 Guernsey，要么是 Holstein。

对于这 $\frac{N(N+1)}{2}$ 个连续子序列中的每一个，计算将其重排为回文串所需的最少交换次数（如果无法重排，则记为 $-1$）。一次交换是指选取子序列中相邻的两头奶牛并交换她们的位置。输出所有这些计数值的总和。

注意，所需交换次数是针对每个连续子序列独立计算的（在拍摄不同照片之间，奶牛会回到她们的初始位置）。

输入格式

由 G 和 H 组成的字符串，表示长度为 $N$ 的队列。

输出格式

所有 $\frac{N(N+1)}{2}$ 个连续子序列的上述计数值之和。

样例

样例输入 1

GHHGGHHGH

样例输出 1

12

说明

前四个连续子序列分别是 G、GH、GHH 和 GHHG。G 和 GHHG 本身就是回文串，因此它们对总和的贡献为 $0$。GHH 可以通过一次交换重排为回文串，因此它对总和的贡献为 $1$。GH 无论经过多少次交换都无法重排为回文串，因此它对总和的贡献为 $-1$。

另一个对总和有贡献的连续子序列是 HHGG。它可以通过两次交换重排为回文串。

子任务

除了样例之外，还有十五个测试用例，分别对应 $N \in [100, 200, 500, 1000, 2000, 5000, 5000, 5000, 5000, 5000, 7500, 7500, 7500, 7500, 7500]$。

题目来源：Mythreya Dharani 和 Benjamin Qi