串联重复

时间限制：2s
空间限制：256MB

题目描述

给定一个仅由小写拉丁字母和问号 ? 组成的字符串 $s$。你可以把每个问号替换为任意一个小写拉丁字母。

若一个字符串的长度为偶数，且它的前一半与后一半完全相同，则称它为串联重复。例如，abab 是串联重复，abba 不是。

子串是原字符串中一段连续的字符。请适当地替换问号，使替换后的字符串中，最长串联重复子串的长度尽可能大，并求这个最大长度。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

接下来 $t$ 行，每行包含一个字符串 $s$，表示一个测试用例。

输出格式

对于每个测试用例，输出一行一个整数，表示替换问号后可以得到的串联重复子串的最大长度。

如果无法得到任何非空的串联重复子串，输出 $0$。

样例输入 1

4
zaabaabz
?????
code?????s
codeforces

样例输出 1

6
4
10
0

数据范围

• 对于所有数据，满足 $1\le t\le1000$。
• 对于所有数据，满足 $1\le \lvert s\rvert\le5000$。
• 所有测试组共同满足 $\sum \lvert s\rvert\le5000$。