Palindrome is a string which reads the same forward and backward. For example,

- The following strings are palindrome: "racecar", "abba", "x"
- The following strings are not palindrome: "abc", "racecars", "xy"

A substring of a string S = S₁S₂... S_N is defined as S' = S_uS_u+1... S_v where 1 ≤ u ≤ v ≤ N.

Little Long just learn about these two definitions and he is eager to study problem of palindrome. He tried to the longest palindrome substring problem and found out that there is a very efficient linear algorithm by Manacher to solve this problem. He read Wikipedia, articles, sample source codes, ... about this algorithm but did not understand it fully. He is still unable to prove the algorithm is actually O(N).

Frustrated, he decided to run the algorithm by hand with small cases to understand it. In the first step, he decided to list all palindrome substrings and count the number of distinct palindrome substrings. Can you help him to do this first step?

Input

The input starts with the number of test - T (T ≤ 150). Then T tests follow. Each test is printed in a line with a non-empty string S. The length of S does not exceed 100.

Output

For each test in the input, print the number of distinct palindrome substrings in a line.

Ex:

• input
  1

  banana
  output
  6

Explanation: a, b, n, ana, nan, anana.

Một chuỗi được gọi là Palindrome khi nó đều giống nhau nếu đọc xuôi hay đọc ngược.

Ví dụ:

• Những chuỗi sau là palindrome: "racecar", "abba", "x"
• Những chuỗi sau không là palindrome: "abc", "racecars", "xy".
  

Cho trước một chuỗi S, nhiệm vụ của bạn là tìm số lượng chuỗi con palindrome riêng biệt của S.

Dữ liệu vào:

- Số nguyên T là số lượng test (T<=150)

- T dòng tiếp theo là các chuỗi không rỗng, không quá 100 kí tự

Dữ liệu ra:

Số lượng chuỗi con palindrome riêng biệt của từng test (ngăn cách nhau bởi dấu xuống dòng)

Ex:

• input
  1

  banana
  output
  6