Harry Potter is searching for the 'Lost Diadem' in Hogwarts to destroy it. Harry has no clue about the diadem so he asked Helena Ravenclaw to help him.
She agrees to help him if he answers her 'Q' queries correctly.
Query is as follows :
An integer 'N' will be given as input for each query. In each query Harry has to tell the smallest integer that should be multiplied with 'N' such that the resulting integer comes out to be a perfect cube.
Since Harry is weak in numbers game he asked for your help.
Input: First line of input contains an integer 'Q' where Q denotes the number of queries. Second line contains an integer 'N'.
Output: For each query print the answer in a single line.
Constraints :
1<=Q<=106
1<=N<=106
Query 1- 3, when multiplied by 9, becomes 27, which is a perfect cube.
Query 2- 8 is already a perfect cube, hence we multiply it by 1.
Query 3- 12, when multiplied by 18, becomes 216, which is a perfect cube.
