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 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)


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

Sample Input

Output for Sample Input

Case 1: 3
Case 2: 4

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

ayushgupta1997: 2017-06-02 07:57:32

easy one :) quadratic ac in one go!!! ,loop costed one tle :(

banneq: 2017-04-18 12:30:08

Wrong output format costed me 5 WA, take care of "Case i: result"!

Saif : 2016-08-18 10:51:44

ac in 1 go!! use recurrence relation!

sharif ullah: 2016-08-04 21:29:49

9th class series summation formula + binary search!!! accepted

Last edit: 2016-08-04 21:31:00
raghav12345: 2015-11-14 10:56:25

easy one apply simple math formula

Manish Das Mohapatra: 2015-08-21 21:16:01

There's space between Colon and Result in the Output format.
1 WA cuz of that.

Ravi Chandra: 2015-08-21 20:51:08

Easy prob....TLE Once..Loop modified...AC

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