Expensive Dinner (Large)

Your friends are all going to one restaurant for dinner tonight. They are very good at math and very particular. Number them starting from 1. Friend $a$ is unhappy unless the total cost of the food ordered so far is a positive integer that is divisible by $a$.

Your friends enter the restaurant one at a time. The moment someone enters, if that person is unhappy, the group calls a waiter immediately.

As long as at least one person in the restaurant is unhappy, one of those unhappy people buys the cheapest single item that makes him or her happy. This continues until nobody in the restaurant is unhappy, and then the waiter leaves. The restaurant sells food at every positive integer price.

Your friends can enter in any order. After a waiter has been called, if more than one person is unhappy, any one of them can be the next to buy something. These choices change how many times the group calls a waiter.

You own the restaurant and your waiters are worn out, so you want the spread of your friends: the difference between the largest number of times they might call a waiter and the smallest number of times they might call a waiter.

The first line contains the number of test cases $T$. Each of the next $T$ lines holds one test case. Each such line contains one integer $N$, the number of friends you have.

Limits

• $1 \le T \le 1000$
• $1 \le N \le 10^{12}$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the spread for that test case.

Take $N = 3$. Suppose the friends arrive in the order [1, 2, 3]. Friend 1 arrives, is unhappy, calls a waiter, and buys an item costing 1. Now nobody is unhappy. Friend 2 arrives next, is unhappy, calls a waiter, and buys an item costing 1, for a total of 2. Now nobody is unhappy. Friend 3 arrives next, is unhappy, calls a waiter, and buys an item costing 1, for a total of 3. Now friend 2 is unhappy and buys an item costing 1, for a total of 4. Now friend 3 is unhappy and buys an item costing 2, for a total of 6. Finally nobody is unhappy, and a waiter was called three times.

Suppose instead that the friends arrive in the order [3, 1, 2]. Friend 3 arrives, is unhappy, calls a waiter, and buys an item costing 3. Now nobody is unhappy. Friend 1 arrives next, and nobody is unhappy. Friend 2 arrives next, is unhappy, calls a waiter, and buys an item costing 1, for a total of 4. Now friend 3 is unhappy and buys an item costing 2, for a total of 6. Now nobody is unhappy, and a waiter was called two times. The spread is 1.