A positive integer n is called cubic-free, if it can't be written in this form n = x*x*x*k, while x is a positive integer larger than 1. For example: 24 = 2*2*2*3, so it's not a cubic-free number, but 18 = 2*3*3, so it is a cubic-free number.
Now give you an integer, you should tell me whether it is a cubic-free number or not.
Input
The first line is an integer T (T <= 10000) means the number of the test cases. The folowing T lines are the test cases, for each test case there is only one line with an integer not greater than 1,000,000,000.
Output
For each test case, output "NO" if the number is cubic-free or else "YES".