1023: SYH’s Easy Decomposing Problem

Memory Limit：256 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：72 Solved：7

Description

SYH gives you an easy target: Decompose a number n into several prime numbers. Can you find the minimal amount of these prime numbers?

Input

The first line conatins an integer T, means the number of test cases. For each test case, the first line contains a single integer n.

Output

For each test case ouput “Case: #x:y” in a single line. x is the test case number (starting from 1), and y is your answer.

Sample Input Copy 

2

2

9

Sample Output Copy 

Case #1: 1
Case #2: 2

HINT

For the first sample, 2 is a prime number itself.

For the second sample, 9 can be decomposed into 2+7.



1 ≤ T ≤ 10, 2 ≤ n ≤ 1012.