Bạn được cho một xâu $s$ bao gồm các chữ cái tiếng Anh viết thường.

Xét một đoạn $[l, r]$ sao cho $2 \le l \le r \le |s|$. Định nghĩa $f(l, r)$ là độ dài của hậu tố dài nhất của xâu con $s[1, l-1]$ sao cho hậu tố này có thể được chia thành các tiền tố của xâu con $s[l, r]$. Nếu không tồn tại hậu tố như vậy thì $f(l, r) = 0$.

Hãy tính tổng $\sum_{l=2}^{|s|} \sum_{r=l}^{|s|} f(l, r)$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^5$) — số lượng bộ dữ liệu kiểm tra. Tiếp theo là mô tả của các bộ dữ liệu.

Dòng duy nhất của mỗi bộ dữ liệu chứa xâu $s$ ($2 \le |s| \le 2 \cdot 10^5$) bao gồm các chữ cái tiếng Anh viết thường.

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

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất — đáp án của bài toán.

Ví dụ

Dữ liệu vào 1

8
aa
ab
ababa
abaaba
abacaba
abaaababaab
aababcabcbc
abcdabcabaabcd

Dữ liệu ra 1

1
0
6
7
0
74
51
20

Ghi chú

Xét bộ dữ liệu thứ ba. Trong trường hợp này, $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$. Vậy đáp án là 6.