题目描述

近期，同学 A 正在研究字符串。某些奇特的字符串引起了他的注意，于是他将这类字符串命名为“准回文串”。

一个字符串 $s$ 是准回文串，当且仅当同时满足以下两个条件：

1. $s$ 中不存在长度大于或等于 $2$ 的连续子串是回文串。
2. 设 $s$ 的长度为 $n$，存在 $l,r$ 满足 $1\leq l\leq r\leq n$，使得将子串 $s[l...r]$ 反转后，$s$ 变为一个回文串。

例如：字符串 aac 不是准回文串，因为它包含长度为 $2$ 的连续子串 aa，该子串是回文串。字符串 abdc 不是准回文串，因为不存在 $l,r$ 使得反转子串 $s[l...r]$ 后 $s$ 成为回文串。字符串 bcabca 是一个准回文串。

现在，给定一个字符串 $T$，同学 A 想知道 $T$ 有多少个连续子串是准回文串。

此处，连续子串仅通过其在原串中的起始和结束位置进行区分。例如，在字符串 aba 中，连续子串 $[1,1]$（第一个 a）与连续子串 $[3,3]$（最后一个 a）被视为两个不同的连续子串，尽管它们都是字符 a。

输入格式

输入一个字符串 $T$（$1\leq |T|\leq 5\times 10^5$）。

输出格式

输出一个整数，表示 $T$ 中是准回文串的连续子串数量。

abcabc

9

abc

3

提示

在第一个样例中，所有长度为 $1$ 的连续子串都是准回文串。在长度大于 $1$ 的子串中，准回文串有 abcab、bcabc 以及 abcabc。

翻译由 DeepSeek V3.2 完成