JPM - Just Primes


This problem is really simple, or is it? Given a positive integer N, calculate the minimum number of distinct primes needed such that their sum equals to N. A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... and so on.

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 ≤ 50,000
  • 1 ≤ N ≤ 50,000
  • Output

    For each test case, first print the case number followed by the minimum number of distinct primes such that their sum equals to N. If N cannot be represented by a summation of distinct primes, then print the case number followed by -1. Refer to the sample input/output for more clarity of the format.

    Sample Input

    10
    1
    2
    3
    10
    27
    100
    1000
    4572
    4991
    49999
    
    

    Sample Output

    Case 1: -1
    Case 2: 1
    Case 3: 1
    Case 4: 2
    Case 5: 3
    Case 6: 2
    Case 7: 2
    Case 8: 2
    Case 9: 3
    Case 10: 1
    

    Challenge

    Too easy? Try the harder version here - Just Primes II


    hide comments
    nadstratosfer: 2021-04-22 13:02:11

    Scape, pls look into recent streak of submissions from CVR College Of Engineering users. Except for Shirisha, they normally code in C or Python, yet here they all switched to Java and magically came up with almost exactly equally performing code.

    -> Yes, looks like its the same code. Disqualified the users manually. Thanks!

    Last edit: 2021-05-03 21:33:16
    rising_stark: 2021-03-17 12:19:08

    Too easy!! Classic coin change problem.


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