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.
The input begins with the number of test cases T. This is followed by T lines each containing N.
Each line containing M.
N is greater than 1 and can have upto 9 decimal digits ending in 1,3,7,or 9.
Problem Setter: Rahul Prakash
Problem Tester: Dhruva Bhaswar