using System; using System.IO; using System.Collections.Generic; using System.Linq; using System.Numerics; namespace No577 { //ref: http://kmjp.hatenablog.jp/entry/2017/10/20/0930 by kmjpさん public class Program { readonly HashSet powerOfPrimes = new HashSet(); void Solve(StreamScanner ss, StreamWriter sw) { //--------------------------------- foreach (var p in new Prime((int)1e3).List) { var t = BigInteger.One; while ((t *= p) <= (long)1e18) powerOfPrimes.Add((long)t); } var Q = ss.Next(int.Parse); for (var i = 0; i < Q; i++) { var N = ss.Next(long.Parse); sw.WriteLine(SolveQuery(N) ? "Yes" : "No"); } //--------------------------------- } bool SolveQuery(long n) { if (n < 4) return false; if (n % 2 == 0) return true; for (var i = 2L; i < n; i <<= 1) { if (IsPowerOfPrime(n - i)) return true; } return false; } bool IsPowerOfPrime(long x) { if (powerOfPrimes.Contains(x) || MillerRabin.IsPrime(x)) return true; for (var a = 2; a <= 5; a++) { Func f = i => BigInteger.Pow(i, a); var lb = BinarySearch.Default(f, 0, (long)1e9).LowerBound(x); if (x == f(lb) && MillerRabin.IsPrime(lb)) return true; } return false; } static void Main() { var ss = new StreamScanner(new StreamReader(Console.OpenStandardInput())); var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false}; new Program().Solve(ss, sw); sw.Flush(); } } public static partial class BinarySearch { public static BinarySearch Default(Func func, long left, long right) where T : IComparable { return new BinarySearch().SetFunc(func).SetInterval(left, right); } public static BinarySearch ToBinarySearch(this IReadOnlyList source) where T : IComparable { return new BinarySearch().SetFunc(x => source[(int)x]).SetInterval(0, source.Count); } } public class BinarySearch where T : IComparable { Func Func { get; set; } = null; long Left { get; set; } = 0; long Right { get; set; } = 0; bool IsOrderAscending { get; set; } = true; public BinarySearch SetFunc(Func func) { Func = func; return this; } public BinarySearch SetInterval(long left, long right) { if (left > right) throw new ArgumentException($"{nameof(left)} <= {nameof(right)}"); Left = left; Right = right; return this; } public BinarySearch SetOrder(bool isOrderAscending) { IsOrderAscending = isOrderAscending; return this; } long BoundToTheRight(Func pred, long left, long right) { while (true) { if (left == right) return right; var mid = (left + right - 1) >> 1; if (pred(mid)) right = mid; else left = mid + 1; } } public long LowerBound(T value) { var sign = IsOrderAscending ? 1 : -1; return BoundToTheRight(x => sign * Func(x).CompareTo(value) >= 0, Left, Right); } public long UpperBound(T value) { var sign = IsOrderAscending ? 1 : -1; return BoundToTheRight(x => sign * Func(x).CompareTo(value) > 0, Left, Right); } public long Range(T vLeft, T vRight) { return Math.Max(0, UpperBound(vRight) - LowerBound(vLeft)); } public long Count(T value) { return Range(value, value); } public bool Contains(T value) { var lb = LowerBound(value); return lb != Right && Func(lb).CompareTo(value) == 0; } } public class Prime { const int CoverIntRangeMax = 46349; readonly List primes; public IReadOnlyList List { get { return primes.AsReadOnly(); } } public Prime(int max = CoverIntRangeMax) { primes = new List {2}; var sieve = new bool[max + 1]; for (var i = 3; i <= max; i += 2) { if (sieve[i]) continue; primes.Add(i); for (var j = i * 3; j <= max; j += i << 1) sieve[j] = true; } } public bool Is(long n) { return n > 1 && List.TakeWhile(p => p * p <= n).All(p => n % p != 0); } public IEnumerable Factorize(long n) { foreach (var p in List.TakeWhile(p => p * p <= n)) { while (n % p == 0) { n /= p; yield return p; } } if (n != 1) yield return n; } public long EulersTotient(long n) { foreach (var x in Factorize(n).Distinct()) n = n / x * (x - 1); return n; } } public static class MillerRabin { const int RandomTestCount = 30; static readonly BigInteger[] BasePrimes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,}; static readonly BigInteger[] WitnessRanges = { 2047, 1373653, 25326001, 118670087467, //3215031751が例外 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, BigInteger.Parse("318665857834031151167461"), BigInteger.Parse("3317044064679887385961981"), }; public static bool IsPrime(BigInteger n) { if (n < 2 || n == 3215031751) return false; if (n < 42) return BasePrimes.Contains(n); if (BasePrimes.Any(p => n % p == 0)) return false; var d = n - 1; while ((d & 1) == 0) d >>= 1; for (var i = 0; i < BasePrimes.Length; i++) { if (!MillerRabinTest(n, d, BasePrimes[i])) return false; if (n < WitnessRanges[i]) return true; } //n > 3.3e24 var random = new Random(); for (var i = 0; i < RandomTestCount; i++) { if (!MillerRabinTest(n, d, random.Next(1, int.MaxValue))) return false; } return true; } static bool MillerRabinTest(BigInteger n, BigInteger d, BigInteger a) { a = BigInteger.ModPow(a, d, n); if (a == 1 || a == n - 1) return true; while ((d <<= 1) < n - 1) { a = a * a % n; if (a == n - 1) return true; } return false; } } public class StreamScanner { static readonly char[] Sep = {' '}; readonly Queue buffer = new Queue(); readonly TextReader textReader; public StreamScanner(TextReader textReader) { this.textReader = textReader; } public T Next(Func parser) { if (buffer.Count != 0) return parser(buffer.Dequeue()); var nextStrings = textReader.ReadLine().Split(Sep, StringSplitOptions.RemoveEmptyEntries); foreach (var nextString in nextStrings) buffer.Enqueue(nextString); return Next(parser); } public T[] Next(Func parser, int x) { var ret = new T[x]; for (var i = 0; i < x; ++i) ret[i] = Next(parser); return ret; } public T[][] Next(Func parser, int x, int y) { var ret = new T[y][]; for (var i = 0; i < y; ++i) ret[i] = Next(parser, x); return ret; } } }