MAIN12A  SelfDescribingSequenceProblem
Everyone loves Swampy. Swampy the Alligator lives under the city and yearns for a more human like existence. Swampy recently learned a new self describing sequence. The sequence is described in blocks where each block has the same number and two consecutive blocks have consecutive numbers in them. To construct the sequence start with '1'. Now '1' means that the following block is of length 1. As '1' was chosen in previous block, therefore '2' is chosen for the current block making the sequence '12'. Now '2' means that the following block is of length 2. As '2' was chosen in previous block, therefore '3' is chosen for the current block making the sequence '1233'. Now '33' means that the following 2 blocks are of length 3. As '3' was chosen in previous block, therefore '4' is chosen for the current block making the sequence '1233444'. And the second '3' in the sequence appends '555' in the already generated sequence, making the sequence '1233444555'.
Input
First line of the input contains an integer T, the number of test cases. Then T test cases follow. Each test case consists of a single integer N.
Output
For each test case, print Case #X: S, where X is the test case number starting from 1, S is the Nth term of the sequence described above.
Example
Input: 4 1 2 3 4 Output: Case #1: 1 Case #2: 2 Case #3: 3 Case #4: 3
Constraints: T <= 10000 1 <= N <= 1000000
hide comments
shaakal:
20190522 05:16:01
easy !!


ankkt16:
20190209 12:02:10
precompute it and beware of format:) 

abhinav_99:
20190112 14:22:47
use vector instead 

vineetpratik:
20160625 17:22:02
pre calculate and store all values in an array and then display it as required by n. 

Siddharth Singh:
20160613 09:24:21
Beware Of The Size Of The Precomputation Array.


Bhuvnesh Jain:
20150716 23:54:07
adhoc. 

Akhil Gupta:
20141219 07:48:51
150th AC. :D 

Ruchir Sharma:
20141218 17:37:44
precomputation rocks.. :D 

knb_dtu:
20140228 21:28:50
wrong format of ans costed me 3 WA's 

Bhavik:
20140222 18:11:48
easy..but implementation is nice:) 
Added by:  Nikunj Jain 
Date:  20120315 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Vaibhav Mittal 