题目描述

给你一个字符串，求所有长度为偶数的前缀在整个字符串出现的次数和。

输入

共一行，一个字符串$s$。

输出

共一行，输出一个整数,代表长度为偶数的前缀在整个字符串出现的次数和。

输入样例

abababc

输出样例

6

提示

【输入样例2】

isdashagayisdashagaydashisnotagaydashisnotagay

【输出样例2】

30

【数据规模】 对于30%的数据，|S| <= 100，保证数据随机。 对于100%的数据，|S| <= 200000。