Given a number N ending in 1,3,7 or 9. There will always exist a number M which when cubed ends with the same original number N. M need never have more digits than N.
Example:- N=123. M=947. (947)^3=849278123. Here (947)^3 ends with N(which is 123).

Write a program which takes N as input and finds M, where M is a number of atmost same number of digits as N, which when cubed ends in N.

Input
The input begins with the number of test cases T. This is followed by T lines each containing N.

Output
Each line containing M.

Constraints
1<=T<=100
N is greater than 1 and can have upto 9 decimal digits ending in 1,3,7,or 9.

Sample Input``` 3 123 45677 771251 ```
Sample Output``` 947 18453 986251 ```
Problem Setter: Rahul Prakash
Problem Tester: Dhruva Bhaswar

Languages: Brain,C,C++,Java,C#,JavaScript,Perl,PHP,Pascal,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0