GOV04 - Quadratic primes

 

Euler published the remarkable quadratic formula:
n² + n + 41
It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.
Using computers, the incredible formula  n²  79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, 79 and 1601, is 126479.
Considering quadratics of the form:
n² + an + b, where |a|  1000 and |b|  1000
where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |4| = 4
Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41.

Using computers, the incredible formula  n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The absolute product of the

coefficients, 79 and 1601, is 126479.

We are interested in producing better quadratic formulas.( which produces more prime numbers )

Considering quadratics of the form:

n² + an + b, where |a| <= R and |b| <= R

( Your input will be the value of R )

where |n| is the modulus/absolute value of n

e.g. |11| = 11 and | - 4| = 4

Find  a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

If two different values of n produces same prime, then we consider those primes as different (i.e. we count them twice) -- look at example.

Remember |a| <= R and |b| <= R

If you get multiple answers, choose the one having smallest value of a. Even then, if you get multiple answers, choose the equation having smallest value of b.

Input

First line of input contains an integer 't' representing the number of test cases. Then 't' lines follows.

Each line contains an integer R.

t<=8000

R<=10000

Output

Output should be of the format:

Integer 1<space>@<space>Integer2

Integer 1: Number of primes equation n2+an+b produces for consecutive value of n, starting from n=0.

Integer 2: absolute product of the coefficients, a and b.

Output of each test case should be on separate line.

 

Scoring

Lesser your fingers work, better it is. :-)

(Minimize your source code length)

Example

Input:
2
41
5

Output:
41 @ 41
5 @ 5 
Explanation:
case 1: a=-1 b=41
case 2: a=-1 b=5 ( Here n=0 and n=1 produces same prime 5, but we will count it twice) 

Added by:Govind Lahoti
Date:2013-04-10
Time limit:1s-2s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Project euler

hide comments
2013-06-16 21:22:37 Aditya Pande
used up all optimizations and got it in 0.00 seconds.
2013-04-12 16:31:48 :-)
@nice problem
I think you have fixed all the bugs.
Finally AC
nice one..

Last edit: 2013-04-11 02:04:25
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.