D. Tandem Repeats?

You are given a string 𝑠, 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 𝑎 is a substring of a string 𝑏 if 𝑎 can be obtained from 𝑏 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 𝑡,(1≤𝑡≤1000) — the number of testcases.

The only line of each testcase contains a string 𝑠 (1≤|𝑠|≤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