Little Cyan Fish rất thích lý thuyết xâu. Hôm nay, Little Cyan Fish mời bạn cùng nghiên cứu biệt danh của con người với cậu ấy.

Trong vũ trụ của Little Cyan Fish, tất cả biệt danh của con người đều có thể được biểu diễn dưới dạng một xâu chỉ chứa các chữ cái Latinh thường (a đến z). Ví dụ, "qingyu", "xiuga" là biệt danh của con người, nhưng "Abacde" không phải là biệt danh của con người.

Little Cyan Fish coi một cái tên $s$ là Lyndon khi và chỉ khi với mỗi hậu tố thực sự* $t$ của $s$, thứ tự từ điển của $s$ nhỏ hơn nghiêm ngặt so với $t$. Ví dụ, "abacde" là một xâu Lyndon, nhưng "qingyu" không phải là một xâu Lyndon (bởi vì xâu ban đầu không nhỏ hơn theo thứ tự từ điển so với hậu tố thực sự "ingyu").

Bây giờ, Little Cyan Fish cho bạn một biệt danh con người $s$, bạn cần tính xem có bao nhiêu cặp $(l, r)$ khác nhau thỏa mãn $1 \le l \le r \le |s|$ sao cho $s[l \dots r]$ là Lyndon.

* Hậu tố thực sự là một hậu tố khác rỗng và không bằng xâu ban đầu. Ví dụ, "qqoj" có $3$ hậu tố thực sự, đó là "j", "oj", và "qoj".

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dữ liệu vào gồm một dòng duy nhất chứa một xâu $s$ ($1 \le |s| \le 2 \times 10^5$), cho biết biệt danh của con người.

Đảm bảo rằng tổng của $|s|$ trên tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên, cho biết câu trả lời.

Ví dụ

Đầu vào 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Đầu ra 1

3
9
27
16
58
32