Cho xâu ~s~, hãy tìm xâu ~p~ dài nhất thỏa mãn các điều kiện:

• ~p~ là xâu con của ~s~
• Không có xâu con khác rỗng của ~p~ là tiền tố của ~s~.
• Không có xâu con khác rỗng của ~p~ là hậu tố của ~s~.

Dữ liệu vào

• Dòng đầu ghi số nguyên dương ~t~ ~(t≤10000)~ cho biết số lượng testcase. ~t~ dòng tiếp theo mỗi dòng ghi một xâu ~s~ ~(|s|≤10^6)~.

Tổng độ dài của ~s~ trong tất cả testcase không quá ~2.10^6~

Trong xâu ~s~ chỉ chứa các ký tự chữ cái latinh in thường.

Kết quả

• Với mỗi testcase in ra độ dài xâu ~p~ tìm được, nếu không tìm được xâu ~p~ thì in ~-1~.

Ví dụ:

Input

2
abcdab
aaa 

Output

2
-1