Note

The execution time limit for this problem is 6000[ms].

Problem Statement

Consider the following problem:

A positive integer $T$ is given at the beginning of the input. Answer $T$ instances of this problem.

Background

Can every even number greater than or equal to $4$ be expressed as a sum of $2$ primes (not necessarily distinct)?

It has apparently been proved in 2014 by Tom$\textrm{\'a}$s Oliveira e Silva, Siegfried Herzog, and Silvio Pardi that no counterexample exists among even numbers up to at least $4 \times 10^{18}$^[1], but whether a counterexample actually exists is not known. In other words, this is an open problem in mathematics, and the conjecture that no counterexample exists is called the Goldbach conjecture.

Since solving the Goldbach conjecture itself is far too difficult, various variants that weaken its claim have been devised. For example, the version that allows a sum of at most $6$ primes instead of exactly $2$ was reportedly proved in 1995 by Olivier Ramar$\textrm{\'e}$^[2].

So what happens if, in exchange for removing the limit on the number of summands, we require that the primes used in the sum be distinct? That is the question we would like you all to consider this time.

Input

For each positive integer $t$ less than or equal to $T$, let $N_t$ denote the input $N$ for the $t$-th problem.

The input is then given from standard input in $2$ lines, in the following format:

• Line $1$ contains $T$, separated by half-width spaces.
• Line $2$ contains $N_t$ for each positive integer $t$ less than or equal to $T$, in increasing order of $t$, separated by half-width spaces.

$T$
$N_1$ $\cdots$ $N_T$

Constraints

The input satisfies the following constraints:

• $T$ is an integer satisfying $1 \leq T \leq 10^5$.
• For every positive integer $t$ less than or equal to $T$, $N_t$ is an integer satisfying $1 \leq N_t$.
• $\sum_{t=1}^{T} N_t \leq 10^{14}$.

Subtasks

This problem has partial scoring based on subtasks.

Output

For each positive integer $t$ less than or equal to $T$, print Yes on line $t$ if $N_t$ can be expressed as a sum of finitely many distinct primes, and No otherwise.

Print a newline at the end.

Sample

8
1 2 3 4 5 6 7 8

No
Yes
Yes
No
Yes
No
Yes
Yes

References

1. Oliveira e Silva, Siegfried Herzog, and Silvio Pardi, Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4 \cdot 10^{18}$, Math. Comp. 83 (2014), pp. 2033--2060.
2. Olivier Ramar$\textrm{\'e}$, On $\textrm{\u{S}}$nirel'man's constant, Annali della Scuola Superiore di Pisa vol. 22, no. 4 (1995), pp. 645--705.