문제

개의 줄마다 영어 대문자로만 이루어진 문자열 가 주어질 때, 각 줄마다 아래 조건을 모두 만족하는 문자열 를 출력하여라.

1. 는 로 시작하여야 한다.
2. 를 뒤에서부터 읽은 문자열 에 대해서도 로 시작하여야 한다.
3. 위 조건을 만족하는 문자열이 여러 가지라면, 가장 길이가 짧은 문자열이 가 된다.

가능한 모든 에 대해서 조건을 만족하는 는 유일함을 증명할 수 있다.

입력

첫 번째 줄에 주어지는 문자열의 개수 가 주어진다.

두 번째 줄부터 개의 줄에 걸쳐 문자열 가 주어진다. 각 줄마다 주어지는 문자열 의 길이는 이상 이하이다.

출력

개의 줄에 걸쳐 주어진 문자열 마다 조건을 모두 만족하는 문자열 를 출력한다.

Note

첫 번째 예제의 정답인 KITPAPTIK는 KITPA로 시작하고, 뒤에서부터 읽은 문자열 KITPAPTIK도 KITPA로 시작합니다.

두 번째 예제에 대해서, BANANANAB도 앞의 조건 두 개를 만족하지만, 더 짧은 문자열 BANANAB도 조건을 만족하므로, 가장 짧은 문자열인 BANANAB가 정답이 됩니다.