题目背景

小 K 正在设计一款自己的文本归档器。

为了压缩文件，他打算寻找文本中相邻出现的两个完全相同的片段。例如，若某段文本可以写成 AA，就可以考虑将它压缩成类似 2(A) 的形式。当片段 A 足够长时，这样做能够节省不少空间。

正式编写压缩程序之前，小 K 想先评估这种方法的潜力：给定一段文本，其中究竟有多少个连续子串能够写成 AA？

请你帮他完成这个统计任务。

题目描述

给定一个仅由英文字母组成的字符串 $S$。

请统计有多少个连续子串可以表示为两个完全相同字符串的连接，即形如

形式化地说，需要统计满足以下条件的区间 $[l,r]$ 的数量：

• $1\le l\le r\le |S|$；
• 子串长度 $r-l+1$ 为偶数；
• 令

则有

相同内容出现在不同位置时，应当分别计数。

例如，字符串 aaaa 中共有 $4$ 个符合条件的子串：三个 aa 和一个 aaaa。

输入格式

输入仅一行，包含一个字符串 $S$。

字符串只包含大写或小写英文字母，并且大小写敏感。例如，字符 A 与字符 a 不相同。

输出格式

输出一个整数，表示形如 AA 的连续子串数量。

样例 #1

输入

abcdefg

输出

0

样例 #2

输入

blabla

输出

1

样例 #3

输入

aCacaacaa

输出

4

数据范围

对于全部数据，保证：

答案可能超过 $32$ 位有符号整数范围，请使用 $64$ 位整数保存。