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).

Simple Repetition

Examples