MAIN12A - SelfDescribingSequenceProblem

no tags 

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: 2019-05-22 05:16:01

easy !!

ankkt16: 2019-02-09 12:02:10

precompute it and beware of format:)

abhinav_99: 2019-01-12 14:22:47

use vector instead

vineetpratik: 2016-06-25 17:22:02

pre calculate and store all values in an array and then display it as required by n.

Siddharth Singh: 2016-06-13 09:24:21

Beware Of The Size Of The Precomputation Array.
Costed Me 3 Very Irritating RE(SIGSEGV)

Bhuvnesh Jain: 2015-07-16 23:54:07

adhoc.

Akhil Gupta: 2014-12-19 07:48:51

150th AC. :D

Ruchir Sharma: 2014-12-18 17:37:44

precomputation rocks.. :D

knb_dtu: 2014-02-28 21:28:50

wrong format of ans costed me 3 WA's

Bhavik: 2014-02-22 18:11:48

easy..but implementation is nice:)


Added by:Nikunj Jain
Date:2012-03-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Vaibhav Mittal