Constructing the Shortest Palindrome

Given a string s, your task is to construct the shortest palindrome by appending characters only to the end of s.

Formally, let the reverse of s be denoted as \(s^R\). You need to find the smallest string \(P\) such that \(P = s + X\) and \(P = P^R\), where \(X\) is a possibly empty string.

For example, if s = ab, the answer is aba.

inputFormat

The first line contains a single integer T representing the number of test cases.

Each of the next T lines contains a non-empty string s.

outputFormat

For each test case, output the shortest palindrome that can be formed by appending characters to the end of the input string. Each result should be printed on a new line.

## sample

1
a

a

</p>