Little Cyan Fish は文字列理論が大好きです。今日、Little Cyan Fish はあなたを誘って一緒に人間のニックネームを研究することにしました。

Little Cyan Fish の宇宙では、人間のニックネームはすべて英小文字（a から z）のみを含む文字列として表されます。例えば、"qingyu" や "xiuga" は人間のニックネームですが、"Abacde" は人間のニックネームではありません。

Little Cyan Fish は、名前 $s$ のすべての真の接尾辞* $t$ に対して、$s$ の辞書順が $t$ よりも真に小さいとき、かつそのときに限り、$s$ を Lyndon であるとみなします。例えば、"abacde" は Lyndon 文字列ですが、"qingyu" は Lyndon 文字列ではありません（元の文字列が真の接尾辞 "ingyu" より辞書順で小さくないためです）。

今、Little Cyan Fish はあなたに人間のニックネーム $s$ を与えます。$1 \le l \le r \le |s|$ かつ $s[l \dots r]$ が Lyndon となるような異なる組 $(l, r)$ がいくつ存在するかを求めてください。

* 真の接尾辞とは、空でなく、かつ元の文字列と等しくない接尾辞のことです。例えば、"qqoj" には $3$ 個の真の接尾辞があり、それらは "j"、"oj"、"qoj" です。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す整数 $T$ ($1 \le T$) が与えられます。

各テストケースについて、入力は人間のニックネームを表す文字列 $s$ ($1 \le |s| \le 2 \times 10^5$) を含む 1 行からなります。

すべてのテストケースにおける $|s|$ の総和は $2 \times 10^5$ を超えないことが保証されます。

出力

各テストケースについて、答えを表す 1 つの整数を含む 1 行を出力してください。

入出力例

入力例 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

出力例 1

3
9
27
16
58
32