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
Bhavik: 2014-02-22 18:11:48

easy..but implementation is nice:)

Vipul Pandey: 2014-01-05 22:19:23

AC on first attempt. There is nothing in the problem if you understand it.

Rishabh Dugar: 2013-07-19 04:43:15

dnt forget format of output costed 1 wa

Hamim Raavi: 2013-06-25 13:00:59

AC test cases:
Input------Output
10..........5
100.........21
1000........86
10000.......356
100000......1479
1000000.....6137

vikash singh: 2013-06-04 20:16:02

getting all correct ans still WA please help!!
id=9419937

Sandeep Pathry: 2013-06-01 10:59:39

My code is working correctly for all test cases... still WA...
Plz Help... ID-9394240

Kartik Khare: 2013-05-31 19:22:49

Everybody's saying its so easy
but i'm just unable to figure out how to generate this whole sequence in code
edit:
just not print "case #" cost me two wrong answers

Last edit: 2013-06-01 08:02:10
Hitman: 2013-05-30 03:47:01

For all those who get AC take it as a moral obligation to provide some hints or test cases to others
Easy One AC in First attempt For n=1000000 ans = 6137

kamalesh: 2013-04-01 06:12:09

easy one :)


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