/+ dub.sdl: name "A" dependency "dcomp" version=">=0.7.3" +/ import std.stdio, std.algorithm, std.range, std.conv; // import dcomp.foundation, dcomp.scanner, dcomp.numeric.primitive, dcomp.numeric.prime; import std.math : pow; bool ck2(long x) { import std.math; if (isPrime(x)) return true; foreach (i; 2..100) { long y = cast(long)(pow(x, 1.0/i) + 0.001); if (!isPrime(y)) continue; long z = 1; foreach (j; 0..i) z *= y; if (z == x) return true; } return false; } bool solve(long x) { if (x == 2) return false; if (x % 2 == 0) return true; long b = 2; while (b < x) { if (ck2(x-b)) return true; b *= 2; } return false; } int main() { Scanner sc = new Scanner(stdin); // Scanner sc = new Scanner(File("tests/Ain0.txt")); int q; sc.read(q); foreach (i; 0..q) { long x; sc.read(x); if (solve(x)) writeln("Yes"); else writeln("No"); } return 0; } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */ // module dcomp.numeric.primitive; import std.traits; import std.bigint; Unqual!T pow(T, U)(T x, U n) if (!isFloatingPoint!T && (isIntegral!U || is(U == BigInt))) { return pow(x, n, T(1)); } Unqual!T pow(T, U, V)(T x, U n, V e) if ((isIntegral!U || is(U == BigInt)) && is(Unqual!T == Unqual!V)) { Unqual!T b = x, v = e; Unqual!U m = n; while (m) { if (m & 1) v *= b; b *= b; m /= 2; } return v; } T powMod(T, U, V)(T x, U n, V md) if (isIntegral!U || is(U == BigInt)) { T r = T(1); while (n) { if (n & 1) r = (r*x)%md; x = (x*x)%md; n >>= 1; } return r % md; } ulong ulongPowMod(U)(ulong x, U n, ulong md) if (isIntegral!U || is(U == BigInt)) { // import dcomp.int128; ulong mul(ulong a, ulong b) { auto u = mul128(a, b); auto v = mul128(div128(u, md), md); return u[0] - v[0]; } x %= md; ulong r = 1; while (n) { if (n & 1) { r = mul(r, x); } x = mul(x, x); n >>= 1; } return r % md; } T lcm(T)(in T a, in T b) { import std.numeric : gcd; return a / gcd(a,b) * b; } T[3] extGcd(T)(in T a, in T b) if (!isIntegral!T || isSigned!T) { if (b==0) { return [T(1), T(0), a]; } else { auto e = extGcd(b, a%b); return [e[1], e[0]-a/b*e[1], e[2]]; } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/ldc/inline.d */ // module dcomp.ldc.inline; version(LDC) { pragma(LDC_inline_ir) R inlineIR(string s, R, P...)(P); } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */ // module dcomp.scanner; // import dcomp.array; class Scanner { import std.stdio : File; import std.conv : to; import std.range : front, popFront, array, ElementType; import std.array : split; import std.traits : isSomeChar, isStaticArray, isArray; import std.algorithm : map; File f; this(File f) { this.f = f; } char[512] lineBuf; char[] line; private bool succW() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (!line.empty && line.front.isWhite) { line.popFront; } return !line.empty; } private bool succ() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (true) { while (!line.empty && line.front.isWhite) { line.popFront; } if (!line.empty) break; line = lineBuf[]; f.readln(line); if (!line.length) return false; } return true; } private bool readSingle(T)(ref T x) { import std.algorithm : findSplitBefore; import std.string : strip; import std.conv : parse; if (!succ()) return false; static if (isArray!T) { alias E = ElementType!T; static if (isSomeChar!E) { auto r = line.findSplitBefore(" "); x = r[0].strip.dup; line = r[1]; } else static if (isStaticArray!T) { foreach (i; 0..T.length) { bool f = succW(); assert(f); x[i] = line.parse!E; } } else { FastAppender!(E[]) buf; while (succW()) { buf ~= line.parse!E; } x = buf.data; } } else { x = line.parse!T; } return true; } int read(T, Args...)(ref T x, auto ref Args args) { if (!readSingle(x)) return 0; static if (args.length == 0) { return 1; } else { return 1 + read(args); } } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */ // module dcomp.foundation; static if (__VERSION__ <= 2070) { /* Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d Copyright: Andrei Alexandrescu 2008-. License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). */ template fold(fun...) if (fun.length >= 1) { auto fold(R, S...)(R r, S seed) { import std.algorithm : reduce; static if (S.length < 2) { return reduce!fun(seed, r); } else { import std.typecons : tuple; return reduce!fun(tuple(seed), r); } } } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/int128.d */ // module dcomp.int128; // import dcomp.array; version(LDC) { // import dcomp.ldc.inline; } version(LDC) version(X86_64) { version = LDC_IR; } ulong[2] mul128(ulong a, ulong b) { ulong[2] res; version(LDC_IR) { ulong upper, lower; inlineIR!(` %r0 = zext i64 %0 to i128 %r1 = zext i64 %1 to i128 %r2 = mul i128 %r1, %r0 %r3 = trunc i128 %r2 to i64 %r4 = lshr i128 %r2, 64 %r5 = trunc i128 %r4 to i64 store i64 %r3, i64* %2 store i64 %r5, i64* %3`, void)(a, b, &lower, &upper); return [lower, upper]; } else version(D_InlineAsm_X86_64) { ulong upper, lower; asm { mov RAX, a; mul b; mov lower, RAX; mov upper, RDX; } return [lower, upper]; } else { ulong B = 2UL^^32; ulong[2] a2 = [a % B, a / B]; ulong[2] b2 = [b % B, b / B]; ulong[4] c; foreach (i; 0..2) { foreach (j; 0..2) { c[i+j] += a2[i] * b2[j] % B; c[i+j+1] += a2[i] * b2[j] / B; } } foreach (i; 0..3) { c[i+1] += c[i] / B; c[i] %= B; } return [c[0] + c[1] * B, c[2] + c[3] * B]; } } ulong div128(ulong[2] a, ulong b) { version(LDC_IR) { return inlineIR!(` %r0 = zext i64 %0 to i128 %r1 = zext i64 %1 to i128 %r2 = shl i128 %r1, 64 %r3 = add i128 %r0, %r2 %r4 = zext i64 %2 to i128 %r5 = udiv i128 %r3, %r4 %r6 = trunc i128 %r5 to i64 ret i64 %r6`,ulong)(a[0], a[1], b); } else version(D_InlineAsm_X86_64) { ulong upper = a[1], lower = a[0]; ulong res; asm { mov RDX, upper; mov RAX, lower; div b; mov res, RAX; } return res; } else { import std.bigint, std.conv; return (((BigInt(a[1]) << 64) + BigInt(a[0])) / BigInt(b)).to!string.to!ulong; } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/array.d */ // module dcomp.array; T[N] fixed(T, size_t N)(T[N] a) {return a;} struct FastAppender(A, size_t MIN = 4) { import std.algorithm : max; import std.conv; import std.range.primitives : ElementEncodingType; import core.stdc.string : memcpy; private alias T = ElementEncodingType!A; private T* _data; private uint len, cap; @property size_t length() const {return len;} bool empty() const { return len == 0; } void reserve(size_t nlen) { import core.memory : GC; if (nlen <= cap) return; void* nx = GC.malloc(nlen * T.sizeof); cap = nlen.to!uint; if (len) memcpy(nx, _data, len * T.sizeof); _data = cast(T*)(nx); } void free() { import core.memory : GC; GC.free(_data); } void opOpAssign(string op : "~")(T item) { if (len == cap) { reserve(max(MIN, cap*2)); } _data[len++] = item; } void insertBack(T item) { this ~= item; } void removeBack() { len--; } void clear() { len = 0; } ref inout(T) back() inout { assert(len); return _data[len-1]; } ref inout(T) opIndex(size_t i) inout { return _data[i]; } T[] data() { return (_data) ? _data[0..len] : null; } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/numeric/prime.d */ // module dcomp.numeric.prime; T[] divisorList(T)(T x) { import std.algorithm : sort; T[] res; for (T i = 1; i*i <= x; i++) { if (x%i == 0) { res ~= i; if (i*i != x) res ~= x/i; } } sort(res); return res; } T[] factorList(T)(T x) { T[] res; for (T i = 2; i*i <= x; i++) { while (x % i == 0) { res ~= i; x /= i; } } if (x > 1) res ~= x; return res; } // import dcomp.numeric.primitive; bool isPrime(ulong n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; long d = n-1; while (d % 2 == 0) d /= 2; ulong[] alist = [2,3,5,7,11,13,17,19,23,29,31,37]; foreach (a; alist) { if (n <= a) break; long t = d; ulong y = ulongPowMod(a, t, n); while (t != n-1 && y != 1 && y != n-1) { y = ulongPowMod(y, 2, n); t <<= 1; } if (y != n-1 && t % 2 == 0) { return false; } } return true; } /* This source code generated by dcomp and include dcomp's source code. dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp) dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt) */