空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Now GGG, who is an expert in the field of biochemistry has found a standard called Sanity Value, or SAN Value for short to calculate the danger level of COVID-19.
The standard has been defined as follow:
The RNA sequence of COVID-19 is represented as a string . The string
can be divided into consecutive and identical substrings without intersection, and its SAN Value(represented as
) is the maximum number of identical substrings we can get among all the divisions of string
.
For example, "ababab" can be divided into "ab", "ab", "ab", so the SAN value of "ababab" is 3. And "ababa" can not be devided into consecutive and identical substrings, so its SAN value of "ababa" is 1.
Now GGG has comfirmed the virus's RNA sequence, can you help him to calculate the maximum SAN Value of all the substrings appearing in the sequence?
输入描述:
The first line
represents the number of testcases.
For each testcase, there is a string
containing only lowercase letters in a line.
输出描述:
For each testcase, output the maximum SAN Valueof all the substrings in
in one line.