Problem Description

A cubic number is the result of using a whole number in a multiplication three times. For example, 3×3×3=27 so 27 is a cubic number. The first few cubic numbers are 1,8,27,64 and 125. Given an prime number p. Check that if p is a difference of two cubic numbers.

Input

The first of input contains an integer T (1≤T≤100) which is the total number of test cases.

For each test case, a line contains a prime number p (2≤p≤1012).

Output

For each test case, output 'YES' if given p is a difference of two cubic numbers, or 'NO' if not.

Sample Input

10 2 3 5 7 11 13 17 19 23 29

Sample Output

NO NO NO YES NO NO NO YES NO NO

题意：给一个素数，问这个素数是否是两个立方数的差。

思路：

对于方程$a^3-b^3=p$，p是个素数，因此把方程进行变形成$a^3 - b^3 = (a-b)*(a^2+ab+b^2)$。

这时候可以发现$b=a-1$，因此问题就变成了找到a，使得方程$a^2+a(a-1)+(a-1)^2 = p$成立。然后进行二分。

#include "bits/stdc++.h"using namespace std;typedef long long LL;bool judge(LL x, LL p) {    return x*(x-1)+x*x+(x-1)*(x-1) >= p;}int main(int argc, char const *argv[]){    int T;    scanf("%d", &T);    while (T--) {        LL p;        scanf("%lld", &p);        LL ub = 1e6 + 10, lb = 0;        LL ans = 0;        while (ub >= lb) {            LL mid = (ub+lb)>>1;            if (judge(mid, p)) {                ans = mid;                ub = mid - 1;            }            else lb = mid + 1;        }        if (ans*(ans-1)+ans*ans+(ans-1)*(ans-1) == p) puts("YES");        else puts("NO");    }    return 0;}