Dinner With Friends

All submissions for this problem are available.
Your friends are all going to a restaurant for dinner tonight. They're all very good at math, but they're all very strange: your ath friend (starting from 1) will be unhappy unless the total cost of the meal is a positive integer, and is divisible by a.
Your friends enter the restaurant one at a time. As soon as someone enters the restaurant, if that person is unhappy then the group will call a waiter immediately.
As long as there is at least one unhappy person in the restaurant, one of those unhappy people will buy the lowestcost item that will make him or her happy. This will continue until nobody in the restaurant is unhappy, and then the waiter will leave. Fortunately, the restaurant sells food at every integer price. See the explanation of the first test case for an example.
Your friends could choose to enter the restaurant in any order. After the waiter has been called, if there is more than one unhappy person in the restaurant, any one of those unhappy people could choose to buy something first. The way in which all of those choices are made could have an effect on how many times the group calls a waiter.
As the owner of the restaurant, you employ some very tired waiters. You want to calculate the spread of your friends: the difference between the maximum number of times they might call a waiter and the minimum number of times they might call a waiter.
Input
The first line of the input gives the number of test cases, T. T test cases follow, each on its own line. Each test case will contain one integer N, the number of friends you have.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the spread for that test case.
Constraints
Should contain all the constraints on the input data that you may have. Format it like:
 1 ≤ T ≤ 1000
 1 ≤ N ≤ 1012
Example
Input: 4 1 3 6 16 Output: Case #1: 0 Case #2: 1 Case #3: 2 Case #4: 5
Explanation
In Case #2, suppose your friends arrive in the order [1, 2, 3]. Then #1 arrives; is unhappy; calls a waiter; and buys something costing 1. Now nobody is unhappy. #2 arrives next; is unhappy; calls a waiter; and buys something costing 1 (for a total of 2). Now nobody is unhappy. #3 arrives next; is unhappy; calls a waiter; and buys something costing 1 (for a total of 3). Now #2 is unhappy, and buys something costing 1 (for a total of 4). Now #3 is unhappy, and buys something costing 2 (for a total of 6). Finally nobody is unhappy, and a waiter was called three times.
Suppose instead that your friends arrived in the order [3, 1, 2]. Then #3 arrives; is unhappy; calls a waiter; and buys something costing 3. Now nobody is unhappy. #1 arrives next; nobody is unhappy. #2 arrives next; is unhappy; calls a waiter; and buys something costing 1 (for a total of 4). Now #3 is unhappy, and buys something costing 2 (for a total of 6). Now nobody is unhappy, and a waiter was called two times. The spread is 1.
Author:  rajat503 
Tags  rajat503 
Date Added:  7022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 