إذا أمكن تقسيم سلسلة إلى الصورة $AABB$، حيث $A$ و$B$ سلسلتان كيفيتان غير فارغتين، فإننا نسمي هذا التقسيم للسلسلة تقسيمًا ممتازًا.

مثلًا، للسلسلة aabaabaa، إذا وضعنا $A=\mathtt{aab}$ و$B=\mathtt{a}$، نجد طريقة لتقسيم هذه السلسلة إلى $AABB$.

قد لا يكون للسلسلة أي تقسيم ممتاز، وقد يكون لها أكثر من تقسيم ممتاز. فمثلًا، إذا وضعنا $A=\mathtt{a}$ و$B=\mathtt{baa}$، أمكن أيضًا تمثيل السلسلة السابقة بالصورة $AABB$؛ أما السلسلة abaabaa فليس لها تقسيم ممتاز.

تُعطى الآن سلسلة $S$ طولها $n$، ونريد حساب العدد الإجمالي للتقسيمات الممتازة من بين جميع طرق تقسيم جميع سلاسلها الجزئية. والمقصود بالسلسلة الجزئية هنا مقطع متصل من السلسلة.

يجب الانتباه إلى ما يلي:

1. نعد السلاسل الجزئية المتطابقة الواقعة في مواضع مختلفة سلاسل جزئية مختلفة، وتُحسب تقسيماتها الممتازة كلها في الإجابة.
2. يُسمح بأن يكون $A=B$ في التقسيم. فمثلًا، للسلسلة cccc التقسيم $A=B=\mathtt{c}$.
3. السلسلة نفسها إحدى سلاسلها الجزئية.

الإدخال

ملف الإدخال هو excellent.in.

يحتوي كل ملف إدخال على عدة حالات اختبار. يحتوي السطر الأول من الملف على عدد صحيح واحد $T$، وهو عدد الحالات. ويُضمن أن $1\le T\le10$.

يحتوي كل من الأسطر الـ $T$ التالية على سلسلة $S$ مؤلفة فقط من أحرف إنجليزية صغيرة، ومعناها كما ورد في وصف المسألة.

الإخراج

ملف الإخراج هو excellent.out.

أخرج $T$ أسطر، يحتوي كل منها على عدد صحيح يمثل عدد التقسيمات الممتازة الإجمالي من بين جميع تقسيمات جميع السلاسل الجزئية للسلسلة $S$.

أمثلة

الإدخال 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

الإخراج 1

3
5
4
7

ملاحظة

نستخدم $S[i,j]$ للدلالة على السلسلة الجزئية من الحرف رقم $i$ إلى الحرف رقم $j$ من السلسلة $S$ (ويبدأ الترقيم من $1$).

في حالة الاختبار الأولى، توجد ثلاث سلاسل جزئية لها تقسيمات ممتازة:

$S[1,4]=\mathtt{aabb}$، وتقسيمها الممتاز هو $A=\mathtt{a}$ و$B=\mathtt{b}$؛

$S[3,6]=\mathtt{bbbb}$، وتقسيمها الممتاز هو $A=\mathtt{b}$ و$B=\mathtt{b}$؛

$S[1,6]=\mathtt{aabbbb}$، وتقسيمها الممتاز هو $A=\mathtt{a}$ و$B=\mathtt{bb}$.

ولا توجد تقسيمات ممتازة لبقية السلاسل الجزئية، لذا فإن إجابة الحالة الأولى هي $3$.

في حالة الاختبار الثانية، توجد فئتان تضمان إجمالًا أربع سلاسل جزئية لها تقسيمات ممتازة:

للسلاسل الجزئية $S[1,4]=S[2,5]=S[3,6]=\mathtt{cccc}$ التقسيم الممتاز نفسه، وهو $A=\mathtt{c}$ و$B=\mathtt{c}$. لكن لأن مواضع هذه السلاسل الجزئية مختلفة، يجب احتسابه ثلاث مرات؛

أما السلسلة الجزئية $S[1,6]=\mathtt{cccccc}$ فلها تقسيمان ممتازان: $A=\mathtt{c}$ و$B=\mathtt{cc}$، و$A=\mathtt{cc}$ و$B=\mathtt{c}$. وهما تقسيمان مختلفان للسلسلة الجزئية نفسها، ويجب احتسابهما كليهما في الإجابة.

لذلك فإن إجابة الحالة الثانية هي $3+2=5$.

في حالة الاختبار الثالثة، لكل من $S[1,8]$ و$S[4,11]$ تقسيمان ممتازان، و$S[1,8]$ هي المثال الوارد في وصف المسألة؛ لذا فإن الإجابة هي $2+2=4$.

في حالة الاختبار الرابعة، لكل من $S[1,4]$ و$S[6,11]$ و$S[7,12]$ و$S[2,11]$ و$S[1,8]$ تقسيم ممتاز واحد، وللسلسلة $S[3,14]$ تقسيمان ممتازان؛ لذا فإن الإجابة هي $5+2=7$.

المثال 2

انظر الملفين excellent/excellent2.in وexcellent/excellent2.ans في مجلد المتسابق.

المثال 3

انظر الملفين excellent/excellent3.in وexcellent/excellent3.ans في مجلد المتسابق.

المهام الفرعية

لجميع حالات الاختبار، يُضمن أن $1\le T\le10$. وتنطبق القيود التالية على حالة إدخال واحدة؛ أي إن جميع حالات الإدخال الـ $T$ في حالة الاختبار نفسها تحقق القيود.

نفترض أن $n$ هو طول السلسلة $S$، ويرد النطاق التفصيلي للبيانات لكل حالة اختبار في الجدول التالي: