Online Programming Server

PP love palindrome very much. He thinks there are some magical power inside a palindrome. Therefore, he thinks a string is more powerful if it contains more palindromic substrings. To study further, he hired you to help him.

Given a string s, PP wants you to count the number of different palindromic substrings of s. A string p is a palindromic substring of s if p is a substring of s and p is a palindrome. Two substring s1 and s2 are different if s1 and s2 has different starting position or different ending position.

The first line contain an integer T, the number of test case.
For each of the following T (1 ≤ 10 ≤ T) lines, each line contains a string s which consists of lowercase letters. (1 ≤ |s| ≤ 2000)

For each test case, output an integer on a line, the number of different palindromic substrings.