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$.
描述
给定一个字符串 $s$，由小写拉丁字母和/或问号组成。
一个串联重复是一个偶数长度的字符串，其前一半等于其后一半。
字符串 $a$ 是字符串 $b$ 的子字符串，如果 $a$ 可以通过从开头删除零个或多个字符和从末尾删除零个或多个字符得到 $b$。
你的目标是以一种方式用一些小写拉丁字母替换每个问号，使得串联重复的最长子字符串长度尽可能最大。
第一行包含一个整数 $t$（$1 \le t \le 1000$）— 测试用例的数量。
每个测试用例的唯一一行包含一个字符串 $s$（$1 \le |s| \le 5000$），仅由小写拉丁字母和/或问号组成。
所有测试用例中字符串的总长度不超过 $5000$。
对于每个测试用例，输出一个整数 — 将字符串中的每个问号用一些小写拉丁字母替换后，串联重复的最长子字符串的最大长度。
如果无法在字符串中生成任何串联重复的子字符串，则输出 $0$。
输入
第一行包含一个整数 $t$（$1 \le t \le 1000$）— 测试用例的数量。
每个测试用例的唯一一行包含一个字符串 $s$（$1 \le |s| \le 5000$），仅由小写拉丁字母和/或问号组成。
所有测试用例中字符串的总长度不超过 $5000$。
输出
对于每个测试用例，输出一个整数 — 将字符串中的每个问号用一些小写拉丁字母替换后，串联重复的最长子字符串的最大长度。
如果无法在字符串中生成任何串联重复的子字符串，则输出 $0$。
4
zaabaabz
?????
code?????s
codeforces
6
4
10
0