Longest Palindromic Substring with Prime Length

You are given a list of strings. For each string, find the length of the longest substring that satisfies both of the following conditions:

• The length of the substring is a prime number. Recall that a number \( p \) is prime if \( p > 1 \) and its only divisors are 1 and \( p \); that is, there exists no \( d \) such that \( 1 < d < p \) and \( d \) divides \( p \).
• The substring is a palindrome; i.e. it reads the same forward and backward.

If no such substring exists in a given string, output -1.

Example: For the string "abacabad", one possible palindromic substring of prime length is "abacaba" of length 7 (since 7 is prime), so the answer is 7.

inputFormat

The first line contains an integer \( T \) denoting the number of test cases. Each of the following \( T \) lines contains a single string \( S \).

outputFormat

For each test case, output an integer on a new line representing the length of the longest palindromic substring whose length is a prime number. If there is no such substring, print -1.

## sample

2
abacabad
abcde

7
-1

</p>