400912: GYM100283 F Bakkar In The Army

Bakkar is now a senior college student studying computer science. And as many students; Bakkar fell in love with one of his finest colleagues Maymona. And as Bakkar has no brothers he is counting on getting an exemption from the military service after graduation. He got engaged to Maymona in their senior year counting on the exemption and a job he will get after graduation at the same place where he was interning last summer.

Well, man does not always get what he wants; the neither planned nor expected happened. Bakkar’s mother is pregnant and will give birth to Hareedy before Bakkar can get his exemption.

Hareedy is now born and unfortunately Bakkar will have to postpone his job and marriage plans for a year as he will serve as a military soldier for one year.

On the first 45 days, soldiers are trained in the military training center. They have to do a variety of exercises daily. One day Bakkar woke up late and didn't appear in the morning lineup at time. His commander is now angry and is going to punish him.

Bakkar is required to perform push-ups (the push-up position is called 6 esta'ed). His commander tells him to do them in reps (consecutive times) and then rest in between them. The commander wants him to follow a strict pattern. Given an upper limit, he will perform reps with increasing number of push-ups (1, 2, 3, ...) to warm up, until he reaches the upper limit. After that, he starts decreasing the number of push-ups per rep until he stops completely (..., 3, 2, 1). After resting, he will repeat the process again but with a higher upper limit. The upper limit starts with 1, and increases each time by a value of 1.

Here are the first 16 reps:

1

1 2 1

1 2 3 2 1

1 2 3 4 3 2 1 ....

The total number of push-ups he does is the sum of all the reps has has done so far. So for example, the total number of push-ups after completing 4 reps = 1+1+2+1 = 5, and after completing 7 reps = 1+1+2+1+1+2+3 = 11.

Bakkar now has to do at least N push-ups. This is very exhausting so he needs to know the minimum number of reps to complete using this pattern to reach his punishment reps.

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,000). Followed by T test cases, each test case will be a single integer N, the number of push-ups Bakkar wants to perform (1  ≤  N  ≤  10¹⁸).

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 single space, then a single integer representing the minimum number of reps needed as described above.

5
6
9
11
21
35

Case 1: 5
Case 2: 7
Case 3: 7
Case 4: 13
Case 5: 19