13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T6fd,

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.

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 $

Tandem Repeats?

Examples