minimal-palindromes-4

Harry and Ron are late for their first ever class at Hogwarts.
It is the tranfiguration class. Professor McGonagall is furious
at both of them for being late. She now asks them to perform a
transfiguration spell successfully if they want to attend the class.
The spell involves long palindromic numbers. 

Palindromes are the numbers that reads the same backward as forward. The spell must be able to reduce a palindromic number to another palindrome which will satisfy the following properties :

1.The new palindrome on multiplying with some number should give
back the original palindrome.

2.The length of the old and new palindrome must be same.

Since Harry and Ron have not studied any Transfiguration spell
before the class, they turn to you for help. Program the
spell that will help them out.

Constraints

1 ≤ T ≤ 10000

1 ≤ Length of Palindrome ≤ 10000

Neither the input nor the output shall have leading zeroes

Input

First line contains T no. of test cases.
The next T lines contain a palindromic number each.

Output

Output the new palindrome of each testcase in a new line.

Problem Setter: Vinay Kumar

UPDATE
The output should not be transfigurable any furthur

SAMPLE INPUT
2
6666
6336

SAMPLE OUTPUT
1111
2112

Explanation

For the first test case, 11116=6666. Also no of digits(6666)==no of digits(1111), therefore 1111 is the answer.
For the second test case, 21123=6336. Also no of digits(2112)== no of digits(6336), therefore 2112 is the answer.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: