Hide

Problem H
Happy Happy Prime Prime

RILEY VASHTEE: [reading from display] Find the next number in the sequence:

313 331 367 ...? What?

THE DOCTOR: 379.

MARTHA JONES: What?

THE DOCTOR: It’s a sequence of happy primes – 379.

MARTHA JONES: Happy what?

THE DOCTOR: Any number that reduces to one when you take the sum of the square of its digits and continue iterating it until it yields $1$ is a happy number. Any number that doesn’t, isn’t. A happy prime is both happy and prime.

THE DOCTOR: I dunno, talk about dumbing down. Don’t they teach recreational mathematics anymore?

Excerpted from “Dr. Who,” Episode 42 (2007).

The number 7 is certainly prime. But is it happy?

\begin{eqnarray*} 7 & \rightarrow & 7^2 = 49 \\ 49 & \rightarrow & 4^2 + 9^2 = 97 \\ 97 & \rightarrow & 9^2 + 7^2 = 130 \\ 130 & \rightarrow & 1^2 + 3^2 = 10 \\ 10 & \rightarrow & 1^2 + 0^2 = 1 \\ \end{eqnarray*}

It is happy :-) As it happens, 7 is the smallest happy prime. Please note that for the purposes of this problem, 1 is not prime.

For this problem you will write a program to determine if a number is a happy prime.

Input

The first line of input contains a single integer $P$, ($1 \le P \le 10\, 000$), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number, $K$, followed by the happy prime candidate, $m$, ($1 \le m \le 10\, 000$).

Output

For each data set there is a single line of output. The single output line consists of the data set number, $K$, followed by a single space followed by the candidate, $m$, followed by a single space, followed by YES or NO, indicating whether $m$ is a happy prime.

Sample Input 1 Sample Output 1
4
1 1
2 7
3 383
4 1000
1 1 NO
2 7 YES
3 383 YES
4 1000 NO

Please log in to submit a solution to this problem

Log in