Product-Equalizable Substrings

You are given an integer T and T strings. For each string, your task is to determine if the string can be partitioned exactly into two equal halves such that the product of the prime numbers mapped to the letters in the first half is equal to that of the second half.

Each lowercase letter from 'a' to 'z' is assigned a distinct prime number (the first 26 prime numbers). For a string s of even length n, let its first half be s[0...n/2-1] and its second half be s[n/2...n-1]. Define the product for a half as:

[ P = \prod_{i=1}^{k} p_{s_i}, ]

where \(p_{s_i}\) is the prime corresponding to the i-th character of the half. If the products of the two halves are equal, then the string is said to be Product-Equalizable and the answer for that string is 1. Otherwise (or if the string’s length is odd), the answer is -1.

Your goal is to output the result for each string on a new line.

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each of the following T lines contains a single string composed of lowercase letters.

outputFormat

For each test case, output 1 if the string can be split into two halves with equal prime products, otherwise output -1. Each result should be printed on its own line.

## sample

3
aabb
cdeffedc
abcdef

-1
1
-1

</p>