Cho xâu ký tự \(s\) bao gồm các ký tự in thường. Nhiệm vụ của bạn là kiểm tra xem ta có thể sắp đặt lại các ký tự trong \(s\) để hai ký tự giống nhau đều không kề nhau hay không?

Đưa ra 1 nếu có thể sắp đặt lại các ký tự trong \(s\) thỏa mãn yêu cầu bài toán, ngược lại đưa ra -1.

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(t\) (\(1 \leq t \leq 100\)).
• Những dòng tiếp theo, mỗi dòng chứa một xâu ký tự \(s\) (\(|s| \leq 10000\)) của mỗi bộ test.

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

3
geeksforgeeks
bbbabaaacd
bbbbb

1
1
-1