Sorry About That, Chief!

Interview

Time limit1sMemory limit1024 MB

Summary

For each value from 2 to 10,000, report whether it is prime or how far it is from the nearest prime.

Level: Easy3 of 10
Topics: Number theory, Brute force
Solved: No attempts yet

Problem

When Dr. Orooji was your age, one of the popular TV shows was "Get Smart!" The main character, Maxwell Smart, a secret agent, had a few catchphrases. We used one of them for the title of this problem and will use a couple more in the output.

A prime number is an integer greater than 1 with only two divisors: 1 and itself. Examples include 5, 11, and 23. Given a positive integer, print a message indicating whether the number is prime or how close it is to a prime.

Input

The first line contains a positive integer $n$ ( $n \le 100$ ), the number of values to check. The next $n$ lines each contain one value. Each value is an integer between 2 and 10,000 (inclusive).

Output

At the beginning of each test case, print "Input value: v", where v is the input value. On the next line, print one of the following two messages.

If the number is a prime, print "Would you believe it; it is a prime!"

If the number is not a prime, print "Missed it by that much (d)!", where d is how close the number is to a prime number. The closest prime may be smaller or larger than the given number.

Leave a blank line after the output for each test case.

Examples1

Example 1

Input

Expected output

Input value: 23
Would you believe it; it is a prime!

Input value: 25
Missed it by that much (2)!

Input value: 22
Missed it by that much (1)!

Input value: 10000
Missed it by that much (7)!