تحب السمكة السماوية الصغيرة (Little Cyan Fish) نظرية السلاسل النصية كثيرًا. اليوم، تدعوك السمكة السماوية الصغيرة لدراسة ألقاب البشر معها.

في عالم السمكة السماوية الصغيرة، يمكن تمثيل جميع ألقاب البشر كسلسلة نصية تحتوي فقط على أحرف لاتينية صغيرة (من a إلى z). على سبيل المثال، "qingyu" و "xiuga" هما لقبان بشريان، لكن "Abacde" ليس لقبًا بشريًا.

تعتبر السمكة السماوية الصغيرة الاسم $s$ سلسلة Lyndon إذا وفقط إذا كان لكل لاحقة فعلية* $t$ من $s$، الترتيب المعجمي لـ $s$ أصغر تمامًا من $t$. على سبيل المثال، "abacde" هي سلسلة Lyndon، لكن "qingyu" ليست سلسلة Lyndon (لأن السلسلة الأصلية ليست أصغر معجميًا من اللاحقة الفعلية "ingyu").

الآن، تعطيك السمكة السماوية الصغيرة لقبًا بشريًا $s$، وعليك حساب كم زوجًا مختلفًا $(l, r)$ يحقق $1 \le l \le r \le |s|$ بحيث تكون $s[l \dots r]$ سلسلة Lyndon.

* اللاحقة الفعلية هي لاحقة غير فارغة لا تساوي السلسلة الأصلية. على سبيل المثال، "qqoj" لها $3$ لواحق فعلية، وهي "j" و "oj" و "qoj".

الإدخال

توجد عدة حالات اختبار. يحتوي السطر الأول من الإدخال على عدد صحيح واحد $T$ ($1 \le T$)، يشير إلى عدد حالات الاختبار.

لكل حالة اختبار، يحتوي الإدخال على سطر واحد به سلسلة نصية $s$ ($1 \le |s| \le 2 \times 10^5$)، تشير إلى اللقب البشري.

من المضمون أن مجموع $|s|$ عبر جميع حالات الاختبار لا يتجاوز $2 \times 10^5$.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا يحتوي على عدد صحيح واحد، يشير إلى الإجابة.

مثال

الإدخال 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

الإخراج 1

3
9
27
16
58
32