Longest Substring Without Repeating Characters

Given a string s of lowercase letters, digits and spaces, print the length of the longest substring that contains no repeated character. Spaces count as characters.

Input

Line 1: t, the number of cases (1 <= t <= 1000).

Then t lines, one string s per line (1 <= |s| <= 2 * 10^5). The total length over one input is at most 10^6.

Output

For each case, one line: one integer.

Note

Read each case as a whole line; do not split on spaces. An O(n^2) solution will time out on the larger tests.

1
abcabcbb

3

1
pwwkew

3

1
bbbbb

1

1
ab ba c

4