Một xâu P được gọi là xâu hạt nhân của xâu S nếu xâu P thỏa mãn hai điều kiện:

• Ghép xâu P một số lần thì nhận được xâu S. (có phân biệt chữ hoa và chữ thường)
• P là xâu ngắn nhất.

Yêu cầu: Cho xâu S có độ dài k (1 <= k <=255). Hãy tìm xâu hạt nhân P.

Dữ liệu vào: File văn bản HATNHAN.INP có cấu trúc như sau:

• Dòng đầu ghi một số nguyên dương N (N <= 10).
• N dòng tiếp theo, mỗi dòng ghi một xâu S.

Dữ liệu ra: File văn bản HATNHAN.OUT ghi N dòng, mỗi dòng ghi xâu P tương ứng với mỗi xâu S.

Ví dụ: