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"입니다.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 단일 정수 $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