Mô tả

Chương trình nhận vào một chuỗi ký tự S và đếm tất cả các xâu con của S mà ký tự đầu và ký tự cuối giống nhau.

Ví dụ:

• Với chuỗi S = "aba", các xâu con có ký tự đầu và cuối giống nhau gồm: "a", "b", "a", "aba". Tổng cộng có 4 xâu con.

Đầu vào

1. Dòng đầu tiên là số lượng bộ test T (1 ≤ T ≤ 100).
2. T dòng tiếp theo, mỗi dòng chứa một chuỗi ký tự S (1 ≤ Length(S) ≤ 10³).

Đầu ra

• Với mỗi chuỗi S, in ra số lượng các xâu con thỏa mãn điều kiện trong một dòng.

Ví dụ

Đầu vào:

2
abcab
aba

Đầu ra:

7
4