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 palindrome substrings.

aba
aa

4
3

译文

CodesOnline