Pasha loves prime numbers$^{\text{∗}}$! Once again, in his attempts to find a new way to generate prime numbers, he became interested in an algorithm he found on the internet:

• To obtain a new number $y$, repeat $k$ times the decimal representation of the number $x$ (without leading zeros).

For example, for $x = 52$ and $k = 3$, we get $y = 525252$, and for $x = 6$ and $k = 7$, we get $y = 6666666$.

Pasha really wants the resulting number $y$ to be prime, but he doesn't yet know how to check the primality of numbers generated by this algorithm. Help Pasha and tell him whether $y$ is prime!

$^{\text{∗}}$An integer $x$ is considered prime if it has exactly $2$ distinct divisors: $1$ and $x$. For example, $13$ is prime because it has only $2$ divisors: $1$ and $13$. Note that the number $1$ is not prime, as it has only one divisor.

Input

Each test consists of several sets of input data. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of sets of input data. The following lines describe the sets of input data.

The first and only line of each data set contains two integers: $x$ and $k$ ($1 \leq x \leq 10^9$, $1 \leq k \leq 7$).

Output

For each set of input data, output «YES» (without quotes) if the resulting number $y$ will be prime, and «NO» otherwise.

You may output «Yes» and «No» in any case (for example, the strings «yES», «yes», and «Yes» will be recognized as positive answers).

Samples

4
52 3
6 7
7 1
1 7

NO
NO
YES
NO