Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Example 1:

Input:  abc
Output: 3

("a", "b", "c")

Example 2:

Input:  aaa
Output: 6

("a", "a", "a", "aa", "aa", "aaa")

Constraints:

• 1 ≤ s.length ≤ 1000
• s consists of lowercase English letters

Input format: A single string.

Output format: Count of palindromic substrings.