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

	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.