PHT - Pigeonhole Tower

no tags 

Pigeon SSNA want to build a tower with some wood walls. Let's describe the tower they want to make:

  1. A Tower can consist of different number of level.
  2. If a tower contain L levels then 1st level must contain L holes, 2nd level L-1, 3rd level L-2 ….. L level contain 1 hole.
  3. Each room contain 3 wood walls.

See the picture below:

3 level 4 level
3 Level Tower 4 Level tower

Now pigeon SSNA has n wood walls. What is maximum number of level he can made.

Input

Input starts with an integer T (≤ 100000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 1012)

Output

For each case of input you have to print the case number and expected answer.

Example

Input:
2
15
24

Output:
Case 1: 3
Case 2: 4

hide comments
akriti1099: 2021-03-15 06:09:30

Be careful about long long, cost me 2 WA :(

ritun_1999: 2020-04-06 04:11:59

My O(1) solution is showing TLE...Please help.

mrdevesh_00: 2019-12-18 20:55:41

AC in one go!!!!

aryan29: 2019-06-01 01:12:01

Waste of time easy question just make a formula

deku__: 2019-05-10 05:38:48

So you are given no. of walls as input and you're expected to find no. of levels. You can use A.P concept to solve it.

kshubham02: 2019-04-14 16:43:09

ok ended up solving without the figure. For the record for level = 3, the tower looks like this -
..........|__|...........
.......|__|__|........
.....|__|__|__|.....
where | and __ denote a wood wall being used.

Last edit: 2019-04-14 16:46:13
kshubham02: 2019-04-14 16:10:39

https://s32.postimg.org/ymsous6cl/image.png
URL broken. Image not visible. Please fix.

silentknight16: 2019-02-18 18:03:02

AC in one go!!!

akt_114: 2018-08-08 20:42:53

AC in one go !!

amankumarkeshu: 2018-05-28 06:18:32

Can anyone see the image of the picture ?


Added by:Ajharul Islam Barid
Date:2014-10-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem