Maximum Repetition Count of a Substring

Problem Description

For a given string, if a substring can be formed by repeating some shorter string (the period) $k$ times ($k\ge 1$), we say the repetition count of that substring is $k$. Define the repetition count of the whole string as the maximum repetition count over all of its substrings.

For example, in the string psdababab2345 the substring ababab is formed by repeating ab $3$ times, so its repetition count is $3$.

You are given $T$ strings; for each, find its repetition count.

Input Format

The first line contains an integer $T$ ($1\le T\le 10^3$), the number of strings.

The next $T$ lines each contain one string consisting only of uppercase / lowercase letters and digits. The length of each string is less than $5\times 10^3$, and $\sum |string|\le 5\times 10^3$ is guaranteed.

Output Format

For each test case, output one integer on a single line, the repetition count of that string.

Sample Input

2
psdababab2345
avabcdad

Sample Output

3
1

Sample Explanation

psdababab2345: the substring ababab repeats ab $3$ times, so the answer is $3$.

avabcdad: there is no substring whose repetition count is greater than $1$, so the answer is $1$.