In the Worthington Labs, scientists were developing an inoculation to suppress the X-gene that gives mutants their abilities, and offer the "cure" to any mutant who wants it. They were creating the cure from the genome of a young mutant named Jimmy, who lived at the Worthington facility on the Alcatraz Island.

This news terrified many mutants. Erik Lehnsherr(Magneto), who aims to conquer the world to enable the mutants to replace humans as the dominant species, takes advantage of the situtation and establishes "Brotherhood of Mutants" to destroy the Worthington facility.

The scientists now have to accelerate the development of the "cure". One of the problems in their To-Do list is to find all the repeated substrings in the genome of Jimmy.

As an example, if the genome is represented as "AAGAAG", there are 5 repeated substrings: "A","AA","AAG","AG","G".

The scientists are counting on you to solve this problem ASAP!!

INPUT
The first line of the input consists of a positive integer, T, specifying the number of test cases. The next T lines contain a non-empty string, S.
The string only consists letters A,C,G and T

CONSTRAINTS
1 <= T <= 100
1 <= |S| <= 100000

OUTPUT
or each test case, print the number of repeated substrings in separate lines.