Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT015J - ACM PTIT 2015 J- Xâu con lặp lại

Cho một xâu S có tối đa 100000 chữ cái. Các xâu con lặp lại được định nghĩa là một đoạn liên tiếp các ký tự được lặp lại ít nhất hai lần trong xâu S (các đoạn có thể chồng lấn lên nhau).

Ví dụ xâu “aabaab” có 5 xâu con lặp lại là “a”; “aa”, “aab”, “ab”, “b”.

Xâu “aaaaa” sẽ có 4 xâu con lặp lại là “a”, “aa”, “aaa”, “aaaa”.

Bài toán đặt ra là cho trước một xâu không quá 100000 ký tự chữ cái, hãy đếm số xâu con lặp lại của xâu đó.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu ghi số bộ dữ liệu (không quá 10).

Mỗi bộ dữ liệu ghi trên một dòng xâu S tương ứng.

Output

Với mỗi bộ dữ liệu, ghi trên một dòng số xâu con lặp lại đếm được. Kết quả được đảm bảo không quá giới hạn số nguyên 32 bít. 

Example

Input:
3
aabaab
aaaaa
AaAaA Output: 5
4
5

Được gửi lên bởi:Admin
Ngày:2015-04-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.