Jika suatu string dapat dipecah menjadi bentuk $AABB$, dengan $A$ dan $B$ sembarang string tidak kosong, maka pemecahan string tersebut kita sebut istimewa.

Sebagai contoh, untuk string aabaabaa, jika kita memilih $A=\texttt{aab}$ dan $B=\texttt{a}$, kita mendapatkan salah satu cara memecah string ini menjadi $AABB$.

Sebuah string mungkin tidak memiliki pemecahan istimewa, atau memiliki lebih dari satu pemecahan istimewa. Misalnya, dengan memilih $A=\texttt{a}$ dan $B=\texttt{baa}$, kita juga dapat menyatakan string di atas sebagai $AABB$; tetapi string abaabaa tidak memiliki pemecahan istimewa.

Sekarang diberikan sebuah string $S$ dengan panjang $n$. Kita perlu mencari jumlah seluruh pemecahan istimewa di antara semua cara memecah semua substringnya. Substring di sini berarti suatu bagian berurutan dari string.

Perhatikan hal-hal berikut:

1. Substring yang sama tetapi muncul di posisi yang berbeda dianggap sebagai substring yang berbeda, dan pemecahan istimewa masing-masing semuanya dihitung dalam jawaban.
2. Dalam sebuah pemecahan, $A=B$ diperbolehkan. Misalnya, cccc memiliki pemecahan $A=B=\texttt{c}$.
3. String itu sendiri juga merupakan salah satu substringnya.

Masukan

Berkas masukan adalah excellent.in.

Setiap berkas masukan berisi beberapa kasus uji. Baris pertama berkas masukan hanya berisi sebuah bilangan bulat $T$, yang menyatakan banyaknya kasus uji. Dijamin $1\le T\le 10$.

Masing-masing dari $T$ baris berikutnya berisi sebuah string $S$ yang hanya terdiri atas huruf kecil bahasa Inggris, dengan arti seperti yang dijelaskan pada soal.

Keluaran

Berkas keluaran adalah excellent.out.

Keluarkan $T$ baris. Setiap baris berisi sebuah bilangan bulat yang menyatakan jumlah pemecahan istimewa di antara semua cara memecah semua substring string $S$.

Contoh

Masukan 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Keluaran 1

3
5
4
7

Catatan

Kita menggunakan $S[i,j]$ untuk menyatakan substring dari karakter ke-$i$ hingga karakter ke-$j$ pada string $S$ (indeks dimulai dari $1$).

Pada kasus uji pertama, ada total $3$ substring yang memiliki pemecahan istimewa:

$S[1,4]=\texttt{aabb}$, dengan pemecahan istimewa $A=\texttt{a}$, $B=\texttt{b}$;

$S[3,6]=\texttt{bbbb}$, dengan pemecahan istimewa $A=\texttt{b}$, $B=\texttt{b}$;

$S[1,6]=\texttt{aabbbb}$, dengan pemecahan istimewa $A=\texttt{a}$, $B=\texttt{bb}$.

Substring lainnya tidak memiliki pemecahan istimewa, sehingga jawaban kasus uji pertama adalah $3$.

Pada kasus uji kedua, ada dua jenis substring, berjumlah total $4$, yang memiliki pemecahan istimewa:

Untuk substring $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$, pemecahan istimewanya sama, yaitu $A=\texttt{c}$, $B=\texttt{c}$. Namun, karena posisi substring-substring ini berbeda, pemecahan tersebut harus dihitung $3$ kali;

Untuk substring $S[1,6]=\texttt{cccccc}$, ada $2$ pemecahan istimewa: $A=\texttt{c}$, $B=\texttt{cc}$ dan $A=\texttt{cc}$, $B=\texttt{c}$. Keduanya merupakan pemecahan berbeda dari substring yang sama dan keduanya juga harus dihitung dalam jawaban.

Jadi, jawaban kasus uji kedua adalah $3+2=5$.

Pada kasus uji ketiga, $S[1,8]$ dan $S[4,11]$ masing-masing memiliki $2$ pemecahan istimewa. $S[1,8]$ adalah contoh dalam deskripsi soal, sehingga jawabannya adalah $2+2=4$.

Pada kasus uji keempat, $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$, dan $S[1,8]$ masing-masing memiliki $1$ pemecahan istimewa, sedangkan $S[3,14]$ memiliki $2$ pemecahan istimewa, sehingga jawabannya adalah $5+2=7$.

Contoh 2

Lihat excellent/excellent2.in dan excellent/excellent2.ans di direktori peserta.

Contoh 3

Lihat excellent/excellent3.in dan excellent/excellent3.ans di direktori peserta.

Subtugas

Untuk semua kasus uji, dijamin $1\le T\le 10$. Semua batasan data berikut berlaku untuk satu kasus masukan, yaitu seluruh $T$ kasus masukan dalam satu kasus uji penilaian memenuhi batasan tersebut.

Misalkan $n$ adalah panjang string $S$. Batasan data terperinci untuk setiap kasus uji penilaian tercantum pada tabel berikut: