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 levels then 1st level must contain  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 4level
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.

Sample Input

Output for Sample Input

2
15
24
Case 1: 3
Case 2: 4

hide comments
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 !!

oneinchatatime: 2018-07-18 18:53:16

Image:
https://odzkskevi.qnssl.com/700b99c8e3b5bedc81e6d93685271f05?v=1528886823

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

Can anyone see the image of the picture ?

minion98: 2017-12-19 16:03:28

@sarthak use type casting

sagar_zhcet: 2017-06-13 21:33:55

please someone explain the sample input and output

Last edit: 2017-06-13 21:34:07
ankit1cool: 2017-06-03 18:40:03

Watch for the "Case" it has capital "C" that caused me 2 WA

vivek_prime: 2017-06-03 10:25:03

what do holes mean here i m not getting this point.


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