Ở một thời xa xưa, trong vùng đất của những bí ẩn và truyền thuyết, có một vương quốc nơi mà các chữ cái không chỉ đơn thuần là những ký hiệu mà còn chứa đựng sức mạnh của tri thức và sự sáng tạo. Người dân vùng đất ấy tin rằng, mọi thông điệp quan trọng đều được ẩn giấu dưới dạng các chuỗi ký tự - những bức tranh tinh vi được xây dựng từ một mảnh ghép nhỏ lặp đi lặp lại nhiều lần theo một mẫu số bí ẩn.

Hôm nay, bạn được giao cho nhiệm vụ đặc biệt: mở khóa bí mật của một thông điệp cổ xưa. Bạn cần phải kiểm tra xem những chuỗi ký tự ~s~ được đưa ra có thể "sống" bằng cách lặp đi lặp lại một mẫu con nào đó không. Nếu có, điều đó đồng nghĩa với việc thông điệp ấy được xây dựng trên nền tảng của một cấu trúc lặp lại, một dấu hiệu cho thấy thông điệp này chứa đựng thông tin quý giá của một nền văn minh cổ xưa.

Input

• Dòng đầu: Gồm một số nguyên dương ~T~ là số lượng xâu. ~(T \leq 100)~
• ~T~ dòng tiếp theo: Mỗi dòng một xâu ~s~ có độ dài không vượt quá ~10^5~.
• Tổng độ dài các xâu ~s~ đã cho có giá trị không vượt quá ~10^6~.

Output

• Gồm ~T~ dòng, với mỗi dòng in ra true nếu thông điệp được xây dựng theo cấu trúc lặp lại, ngược lại in ra false.

Sample Input

4
abab
aba
abcabcabcabc 
abba

Sample Output

true
false
true
false

Constraints

• ~30\%~ số test đầu tiên tương ứng với ~30\%~ số điểm có ~|s| \leq 10^2~.
• ~40\%~ số test tiếp theo tương ứng với ~40\%~ số điểm có ~|s| \leq 10^4~
• ~30\%~ số test cuối cùng tương ứng với ~30\%~ không có ràng buộc gì thêm.