소문자 영어 알파벳으로 이루어진 문자열 $s$가 주어진다.

$2 \le \ell \le r \le |s|$를 만족하는 구간 $[\ell, r]$을 고려하자. $f(\ell, r)$을 부분 문자열 $s[\ell, r]$의 접두사들로 나눌 수 있는 부분 문자열 $s[1, \ell-1]$의 가장 긴 접미사의 길이라고 정의하자. 만약 그러한 접미사가 없다면 $f(\ell, r) = 0$이다.

다음 합을 구하시오. $$\sum_{\ell=2}^{|s|} \sum_{r=\ell}^{|s|} f(\ell, r)$$

입력

첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \le t \le 10^5$)가 주어진다. 각 테스트 케이스에 대한 설명이 이어진다.

각 테스트 케이스의 유일한 줄에는 소문자 영어 알파벳으로 이루어진 문자열 $s$ ($2 \le |s| \le 2 \cdot 10^5$)가 주어진다.

모든 테스트 케이스에 대한 $|s|$의 합은 $2 \cdot 10^5$를 넘지 않음이 보장된다.

출력

각 테스트 케이스마다 문제의 정답인 정수 하나를 출력한다.

예제

입력 1

8
aa
ab
ababa
abaaba
abacaba
abaaababaab
aababcabcbc
abcdabcabaabcd

출력 1

1
0
6
7
0
74
51
20

참고

세 번째 테스트 케이스를 고려해 보자. 이 경우 $f(2, 2) = 0, f(2, 3) = 0, f(2, 4) = 0, f(2, 5) = 0, f(3, 3) = 0, f(3, 4) = 2, f(3, 5) = 2, f(4, 4) = 0, f(4, 5) = 2, f(5, 5) = 0$이다. 따라서 정답은 6이다.