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