## 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 tracyyi: 2022-06-29 10:39:19 Oops, "distinct primes", I missed it. tracyyi: 2022-06-29 04:01:09 Is Goldbach conjecture working here? Last edit: 2022-06-29 05:26:35 David: 2022-02-24 21:34:38 @thanhdatmu2003 The minimum number of distinct primes that sums to 4991 = 3. There is no way to sum 2 primes to equal 4991. I count 13,396 ways (using the restriction p1 < p2 < p3) to sum 3 distinct primes to equal 4991. Here are a few examples: 3 + 19 + 4969 = 4991 3 + 31 + 4957 = 4991 3 + 37 + 4951 = 4991 1627 + 1667 + 1697 = 4991 1637 + 1657 + 1697 = 4991 thanhdatmu2003: 2021-12-13 09:02:36 why 4991 is 3 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.