Description

Given a string S, calculate the number of contiguous substrings in S that are palindromes.

Input Format

The input contains multiple test cases. Each input is a non-empty string with a length not exceeding 5000.

Output Format

For each input, output the number of palindromic substrings.

aba
aa

4
3

来源

CodesOnline