codeforces#P1948D. Tandem Repeats?

    ID: 34522 远端评测题 2000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>brute forcedpexpression parsingstringstwo pointers

Tandem Repeats?

Description

You are given a string $s$, consisting of lowercase Latin letters and/or question marks.

A tandem repeat is a string of an even length such that its first half is equal to its second half.

A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Your goal is to replace each question mark with some lowercase Latin letter in such a way that the length of the longest substring that is a tandem repeat is maximum possible.

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

The only line of each testcase contains a string $s$ ($1 \le |s| \le 5000$), consisting only of lowercase Latin letters and/or question marks.

The total length of the strings over all testcases doesn't exceed $5000$.

For each testcase, print a single integer — the maximum length of the longest substring that is a tandem repeat after you replace each question mark in the string with some lowercase Latin letter.

If it's impossible to make any tandem repeat substrings in the string, print $0$.

Input

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

The only line of each testcase contains a string $s$ ($1 \le |s| \le 5000$), consisting only of lowercase Latin letters and/or question marks.

The total length of the strings over all testcases doesn't exceed $5000$.

Output

For each testcase, print a single integer — the maximum length of the longest substring that is a tandem repeat after you replace each question mark in the string with some lowercase Latin letter.

If it's impossible to make any tandem repeat substrings in the string, print $0$.

4
zaabaabz
?????
code?????s
codeforces
6
4
10
0