#include <bits/stdc++.h> using namespace std; int main() { char a[5001]; int t,i,j,m,s; scanf("%d",&t); while(t--) { scanf("%s",a); int len=strlen(a); vector<vector<int > > b(len, vector<int>(len, 0)); i=0; while(i<strlen(a)) { b[i][i]=1; i++; } s=len; m=2; while(m<=len) { i=0; while(i<=len-m) { j=i+m-1; if(a[i]==a[j]) { if(m==2 or b[i+1][j-1]==1) { b[i][j]=1; s++; } } i++; } m++; } printf("%d\n",s); } return 0; }