Smallest Palindrome Extension

Given a string s, your task is to append the minimum number of characters at the end of s so that the resulting string becomes a palindrome.

A palindrome is a string that reads the same forward and backward. For example, if s = "abb", by appending 'a' to the end, we get "abba", which is a palindrome.

The challenge is to find the smallest extension such that the new string is palindromic.

Note: The appended characters must be inserted only at the end of the string.

The algorithm can be conceptualized as follows:

For a given string \( s \) of length \( n \), find the smallest index \( i \) (with \( 0 \leq i < n \)) such that the substring \( s[i \ldots n-1] \) is a palindrome. Then, the answer is \( s + \text{reverse}(s[0 \ldots i-1]) \).

All formulas are given in \( \LaTeX \) format.

inputFormat

The first line contains a single integer \( T \) denoting the number of test cases.

Each of the following \( T \) lines contains a non-empty string \( s \) consisting of lowercase letters.

outputFormat

For each test case, output a single line containing the smallest palindrome you can obtain by appending characters to the end of the input string \( s \).

## sample

4
abb
aab
abc
racecarer

abba
aabaa
abcba
racecareracecar

</p>