Cho một chuỗi ký tự S gồm toàn chữ cái Tiếng Anh in thường, hãy tìm vị trí đầu tiên của ký tự xuất hiện duy nhất một lần trong S. Nếu không có ký tự nào như vậy thì in ra số -1.

Input

• Dòng đầu tiên chứa số nguyên k (1 ≤ k ≤ 100) là số truy vấn.
• Tiếp theo là k dòng, mỗi dòng chứa một truy vấn là một chuỗi ký tự S có độ dài không quá 10⁴.

Output

ghi ra k dòng, trong đó dòng thứ i trả lời cho truy vấn thứ i theo yêu cầu của đề bài.

Giới hạn:

Gọi N là độ dài của chuỗi ký tự S;
• Có 50% số test ứng với 50% số điểm với N ≤ 10²;
• Có 50% số test còn lại ứng với 50% số điểm không có giới hạn gì thêm.

Ví dụ:

Input

5
axyxybccb
abcdeffavbcde
ababab
b
abcabctyyy

Output

1
9
-1
1
7