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:

+ Dòng đầu ghi số nguyên dương \(t\ (t \leq 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| \leq 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	Output
2 abcdab aaa	2 -1