Nếu một xâu có thể được tách thành dạng $AABB$, trong đó $A$ và $B$ là các xâu không rỗng bất kỳ, ta gọi cách tách xâu này là một cách tách xuất sắc.

Ví dụ, với xâu aabaabaa, nếu đặt $A=\texttt{aab}$, $B=\texttt{a}$, ta tìm được một cách tách xâu này thành $AABB$.

Một xâu có thể không có cách tách xuất sắc nào, hoặc có nhiều hơn một cách tách xuất sắc. Chẳng hạn, nếu đặt $A=\texttt{a}$, $B=\texttt{baa}$, ta cũng có thể biểu diễn xâu trên bằng $AABB$; nhưng xâu abaabaa không có cách tách xuất sắc.

Bây giờ cho một xâu $S$ có độ dài $n$. Ta cần tìm tổng số cách tách xuất sắc trong tất cả các cách tách của mọi xâu con của nó. Ở đây, xâu con là một đoạn liên tiếp trong xâu.

Cần chú ý những điều sau:

1. Các xâu con giống nhau xuất hiện ở vị trí khác nhau được xem là những xâu con khác nhau; các cách tách xuất sắc của chúng đều được tính vào đáp án.
2. Trong một cách tách, cho phép $A=B$. Ví dụ, cccc có cách tách $A=B=\texttt{c}$.
3. Bản thân một xâu cũng là một xâu con của chính nó.

Dữ liệu vào

Tệp đầu vào là excellent.in.

Mỗi tệp đầu vào chứa nhiều bộ dữ liệu. Dòng đầu tiên của tệp chỉ chứa một số nguyên $T$, biểu diễn số bộ dữ liệu. Bảo đảm $1\le T\le 10$.

Trong $T$ dòng tiếp theo, mỗi dòng chứa một xâu $S$ chỉ gồm chữ cái tiếng Anh viết thường, có ý nghĩa như trong đề bài.

Dữ liệu ra

Tệp đầu ra là excellent.out.

In $T$ dòng, mỗi dòng chứa một số nguyên biểu diễn tổng số cách tách xuất sắc trong tất cả các cách tách của mọi xâu con của xâu $S$.

Ví dụ

Dữ liệu vào 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Dữ liệu ra 1

3
5
4
7

Ghi chú

Ta dùng $S[i,j]$ để biểu diễn xâu con từ ký tự thứ $i$ đến ký tự thứ $j$ của xâu $S$ (đánh số từ $1$).

Trong bộ dữ liệu thứ nhất, có tổng cộng $3$ xâu con có cách tách xuất sắc:

$S[1,4]=\texttt{aabb}$, cách tách xuất sắc là $A=\texttt{a}$, $B=\texttt{b}$;

$S[3,6]=\texttt{bbbb}$, cách tách xuất sắc là $A=\texttt{b}$, $B=\texttt{b}$;

$S[1,6]=\texttt{aabbbb}$, cách tách xuất sắc là $A=\texttt{a}$, $B=\texttt{bb}$.

Các xâu con còn lại không có cách tách xuất sắc, nên đáp án của bộ dữ liệu thứ nhất là $3$.

Trong bộ dữ liệu thứ hai, có hai loại, tổng cộng $4$ xâu con có cách tách xuất sắc:

Với các xâu con $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$, các cách tách xuất sắc của chúng giống nhau, đều là $A=\texttt{c}$, $B=\texttt{c}$, nhưng vì những xâu con này ở vị trí khác nhau nên phải tính $3$ lần;

Với xâu con $S[1,6]=\texttt{cccccc}$, có $2$ cách tách xuất sắc: $A=\texttt{c}$, $B=\texttt{cc}$ và $A=\texttt{cc}$, $B=\texttt{c}$. Đây là các cách tách khác nhau của cùng một xâu con và đều phải tính vào đáp án.

Vì vậy, đáp án của bộ dữ liệu thứ hai là $3+2=5$.

Trong bộ dữ liệu thứ ba, $S[1,8]$ và $S[4,11]$ mỗi xâu có $2$ cách tách xuất sắc, trong đó $S[1,8]$ là ví dụ trong phần mô tả bài toán, nên đáp án là $2+2=4$.

Trong bộ dữ liệu thứ tư, $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$, $S[1,8]$ mỗi xâu có $1$ cách tách xuất sắc, còn $S[3,14]$ có $2$ cách tách xuất sắc, nên đáp án là $5+2=7$.

Ví dụ 2

Xem excellent/excellent2.in và excellent/excellent2.ans trong thư mục của thí sinh.

Ví dụ 3

Xem excellent/excellent3.in và excellent/excellent3.ans trong thư mục của thí sinh.

Nhiệm vụ con

Với mọi bộ kiểm thử, bảo đảm $1\le T\le 10$. Các giới hạn dưới đây áp dụng cho từng bộ dữ liệu đầu vào riêng lẻ, tức là cả $T$ bộ dữ liệu trong cùng một bộ kiểm thử đều thỏa mãn các giới hạn.

Giả sử $n$ là độ dài của xâu $S$. Phạm vi dữ liệu chi tiết của từng bộ kiểm thử được cho trong bảng sau: