D. 串联重复串？

单个测试点时间限制： $2$ 秒 单个测试点内存限制： $256$ 兆字节

给定一个字符串 $s$ ，由小写英文字母和问号 ? 组成。

串联重复串是指一个长度为偶数的字符串，满足它的前半部分与后半部分完全相同。

如果字符串 $a$ 可以通过删除 $b$ 开头若干个（可以是 $0$ 个）字符和结尾若干个（可以是 $0$ 个）字符得到，那么 $a$ 是 $b$ 的一个子串。

你的任务是将每个问号替换成某个小写英文字母，使得字符串中最长的串联重复子串的长度尽可能大。

输入格式

第一行包含一个整数 $t$ （ $1\le t\le 1000$ ）—— 测试用例数量。

每个测试用例占一行，包含一个字符串 $s$ （ $1\le |s|\le 5000$ ），仅由小写字母和/或问号组成。

所有测试用例的字符串总长度不超过 $5000$ 。

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

如果无法构造出任何串联重复子串，输出 $0$ 。

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