JPM2 - Just Primes II


Given a positive integer N, calculate the minimum number of distinct primes required such that their sum equals to N. Also calculate the number of different ways to select these primes. Two ways are considered to be different iff there exists at least one prime in one set not existing in the other.

Input

The first line contains an integer T, denoting the number of test cases. Each of the next subsequent T lines contain a positive integer N.

Constraints

  • 1 ≤ T ≤ 500,000
  • 1 ≤ N ≤ 500,000

Output

For each test case, output two integers X and Y separated by a single space. X denotes the minimum number of distinct primes required such that their summation equals to N, and Y is the number of ways to select these primes. If it is not possible to express N as a summation of distinct primes, set X and Y to -1 and output them. You can safely assume that the answer will always fit in a signed 32 bit integer.

Sample Input

20
1
2
10
27
100
666
1000
1729
4572
4991
10000
100000
480480
482790
499799
499847
499901
499979
499999
500000

Sample Output

-1 -1
1 1
2 1
3 3
2 6
2 31
2 28
3 2393
2 110
3 13396
2 127
2 810
2 8499
2 8291
3 31121027
3 31139901
3 31124665
1 1
3 30974053
2 3052

Warm Up

Too hard? Try the easier version here - Just Primes


hide comments
[Lakshman]: 2021-06-05 17:36:21

Finally got AC ;)

-> Great work, congrats!

Last edit: 2021-09-02 18:52:07
rising_stark: 2021-03-17 12:52:51

Even the dp solution here is taking around 100s!!!!!

-> Not the classic coin change problem this time :)

Last edit: 2021-03-21 22:54:19
[Lakshman]: 2021-03-13 13:52:12

Is there a way to solve this without FFT? I have a semi brute force that takes 15s on SPOJ.

-> I don't think so. Of course you can use Karatsuba or any other faster multiplication techniques instead of FFT, but the underlying idea would be the same.

Last edit: 2021-03-21 22:55:02

Added by:sgtlaugh
Date:2021-02-25
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem