# Cube

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