78. Ahmed's Kindergarten

Problem Statement:
Ahmed Abdelsadek is an ICPC world finalist and a previous student of coach Fegla. He is now a research assistant at Simon Fraser University in Canada. And to keep himself busy and make extra money, Ahmed runs a kindergarten in the afternoon. Every day, each child is given a number based on the order he arrived in (relative to other children). So in a given day the first child that comes to the kindergarten is given the number 1, the next child is given the number 2 and so on. One of the major problems Ahmed is facing is that children are always fighting. He also noticed a weird pattern for their fights: every 2 kids whose numbers add up to a prime number fight together. He needs to prepare for future fights, and asked for your help. Assuming that this pattern is actually true, and given the number of children arriving to the kindergarten today, Can you tell him the number of possible fights today?

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Followed by T test cases.

Each test case is a single line containing a positive integer N representing the number of children on a particular day. (1 ≤ N ≤ 105)

Output Format:
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1), followed by a space, followed by R which is the number of pairs of children that could fight on that day.

Sample Input:
4 3 5 57 45

Sample Output:
Case 1: 2 Case 2: 5 Case 3: 381 Case 4: 247

 Added by: ahmed_aly Added at: 2014-04-27 04:52:01 UTC Time Limit: 3 seconds Partial score: No Source: ACM Jordanian Collegiate Programming Contest 2013