Palindromic Naming Convention
In Strangeland, people name their child in a cute way. I'm sure you already know the way by the problem name. But still it's my duty to let you know. Basically, while naming their child, they must follow a convention, a.k.a. Palindromic Naming Convention as given below:
- Every name contains two parts, First Name and Last Name. And people are usually called by their Last Name.
- The concatenation of First Name and Last Name has to be a palindrome.
In case you don't know what palindrome is, please read the note section.
Luimas and Aliban were two great competitive programmers in their University life. Later they got married and moved to Strangeland for their job purpose. Aliban recently gave birth to a pretty baby girl. As per the rules, they must follow the naming convention of Strangeland to name their daughter.
You know it's too simple for competitive programmers to deal with the Palindromic Naming Convention. So they decided that, as a father Luimas will choose the First Name and as a mother Aliban will choose the Last Name.
As per the decision is taken, Luimas instantly chose the First Name. Now it's Aliban's turn to choose the Last Name, but she is too busy in caring her new born baby. So she asks you to help her choosing a non-empty Last Name such that it must meet the 2nd rule of the convention and she wants the Last Name as small as possible.
Input
Input begins with an integer T (0 < T ≤ 10), the number of test cases.
Each test case contains the first name of the baby as a string, S (1 ≤ |S| ≤ 105) consisting of only lowercase Latin letters.
Output
Print space separated first name and last name in a single line for each test case. See the samples for exact formatting.
Sample
| Input | Output |
|---|---|
2 abcd aaa | abcd cba aaa a |
A string is called palindrome if it reads the same from left to right and from right to left. For example "kazak ", "ooo " and "mikhailrubinchikkihcniburliahkim " are palindromes, but strings "abb " and "ijk " are not.
