CPU: 1.5s
Memory: 1024MB
একটি স্ট্রিংকে একটি ধনাত্মক পূর্ণসংখ্যা দিয়ে গুণ করার পদ্ধতিটি বিবেচনা করি। একটি স্ট্রিং s এবং একটি ধনাত্মক পূর্ণসংখ্যা n এর গুণফলকে s*n দিয়ে প্রকাশ করা হয় এবং s কে n সংখ্যক বার পুনরাবৃত্তি করার মাধ্যমে এটি পাওয়া যায়। উদাহরণস্বরূপ, “abc” * 3 = “abcabcabc” .
এই সমস্যাটিতে একটি স্ট্রিং s দেওয়া থাকবে। তোমাকে সর্বনিম্ন দৈর্ঘ্যবিশিষ্ট স্ট্রিং p খুঁজে বের করতে হবে, যাতে একটি ধনাত্মক পূর্ণসংখ্যা k থাকে যার জন্য p * k এবং s সমান হয়।
Consider the operation of multiplying a string by a positive integer. The product of a string s and a positive integer n is denoted by s * n . This product is obtained by repeating s, n times. For example, “abc” * 3 = ”abcabcabc”.
In this problem, a string s is given. You have to find string p of minimum length such that there exists a positive integer k for which p * k equals s.
ইনপুটের বর্ণনা
ইনপুটের প্রথম লাইনে টেস্টকেসের সংখ্যা T দেওয়া থাকবে। এর পরে T টি টেস্টকেসের বর্ণনা থাকবে। প্রতিটি টেস্টকেসে একটি লাইনে একটি শব্দ s দেওয়া থাকবে, যা হল প্রদত্ত স্ট্রিং।
Input
The first line of the input gives the number of test cases, T. Then T test cases follow. Each will consist of one line containing a single word s, which is the given string.
Limits:
1 <= T <= 20
Dataset #1: ( 30 points )
1<=|s|<=103
Dataset #2: ( 30 points )
1<=|s|<=105
Dataset #3: ( 40 points )
1<=|s|<=106
অাউটপুটের বর্ণনা
প্রতিটি টেস্টকেসের জন্য একটি লাইনে একটি শব্দ p আউটপুট দিতে হবে, যেখানে p হল সর্বনিম্ন দৈর্ঘ্যের স্ট্রিং যাকে একটি পূর্ণসংখ্যা দিয়ে গুণ করলে s পাওয়া যায় ।
Output
For each test case, output one line containing a single word p of minimum length such that there exists a positive integer k for which p * k equals s.
Sample
| Input | Output |
|---|---|
| 10 ABAB ABABABAB AAA ABC A ASAASA ASDASASDAS ASDAS ASDA AASAAASA | AB AB A ABC A ASA ASDAS ASDAS ASDA AASA |