Bina Nusantara Programming Contest for High School Student (BNPC HS) 2009

Problem B

Menghitung Palindrome

Time Limit: 3s

Palindrome adalah sebuah kata yang dibaca sama, baik dari depan ataupun dari belakang. Contoh: "MALAM", "ADA", "ABBA". Anda akan diberikan sebuah string S yang panjangnya tidak lebih dari 100 karakter dan hanya terdiri dari huruf kapital, hitung ada berapa substring (potongan string) dari S yang merupakan palindrome.

Input

Input diawali oleh satu baris dengan satu angka, T yang menandakan jumlah test case.

Setiap test case berisi sebuah string S yang panjangnya antara 1 sampai 100 karakter, inklusif. String S hanya disusun atas huruf kapital.

Output

Output terdiri atas tepat T baris (satu baris per test case), dimana setiap baris berisi tepat satu bilangan bulat yang menyatakan jumlah substring dari S yang palindrome.

Sample Input	Output for Sample Input
3 MAKAN MALAM MIMPI	6 7 6

Penjelasan untuk sample case 1:

Substring dari "MAKAN" adalah:

substring dengan panjang 1: M, A, K, A, N. Kelimanya adalah palindrome.
substring dengan panjang 2: MA, AK, KA, AN. Tidak ada palindrome.
substring dengan panjang 3: MAK, AKA, KAN. Hanya AKA yang merupakan palindrome.
substring dengan panjang 4: MAKA, AKAN. Tidak ada palindrome.
substring dengan panjang 5: MAKAN. Tidak ada palindrome.

Sehingga total substring dari MAKAN yang merupakan palindrome adalah 6 (M, A, K, A, N, AKA).