给你一个字符串 $$$s$$$,由小写拉丁字母和/或问号组成。
串联重复是一个偶数长度的字符串,其前半部分等于后半部分。
字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
您的目标是用一些小写拉丁字母替换每个问号,以使串联重复的最长子字符串的长度尽可能最大。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 5000$$$),仅由小写拉丁字母和/或问号组成。
所有测试用例的字符串总长度不超过 $$$5000$$$。
输出
对于每个测试用例,打印一个整数 - 将字符串中的每个问号替换为某个小写拉丁字母后串联重复的最长子字符串的最大长度。
如果不可能在字符串中产生任何串联重复子字符串,则打印 $$$0$$$。
示例
输入 #1
4 zaabaabz ????? code?????s codeforces
输出 #1
6 4 10 0