题目描述

给定一个字符串 s ，输出有多少个区间对应的子串，是回声子串。

对于一个长度为偶数的非空子串 t ，如果该子串的前一半与后一半相同，则认为是回声子串。

例如：s = "goodgoodstudy"，其中 [2,3] 上的子串 "oo" 是回声子串，[1,8] 上的 "goodgood" 也是回声子串，但 [3,6] 上的子串 "odgo" 则不是。

输入

输入一行，一个字符串 s。

输出

输出一行，一个整数，表示 s 中回声子串的数量。

样例1

goodgoodstudy

3

数据范围

对于所有测试点，保证1<=|s|<=5000 ， s中仅包含小写字母。