Problems
10120 - N'th Unlucky Number

N'th Unlucky Number

Time Limit: 1 sec

The Problem

Unlucky numbers consists of exactly those positive integers that are powers of 13 (such as 130 = 1 and 133 = 2197) and those that are a sum of unique powers of 13 (such as 170 = 130 + 132 or 182 = 131 + 132, but not 26 = 131 + 131). The sequence

1, 13, 14, 169, 170, 182, 183, 2197, 2198, 2210

shows the first 10 unlucky numbers.

Given an integer number N, you need to find the Nth unlucky number.

The Input

The first line contains an integer number T, which indicates the number of test cases (0<T<10000). Each test case is given in one line. This line contains a positive integer number N (0<N<60000).

The Output

For each test case, print a single line “Case X: U”, here X is the case number start from 1 to T and U is the Nth unlucky number.

Sample Input

3

1

4

6

Sample Output

Case 1: 1

Case 2: 169

Case 3: 182

[University Level]

Inter School & College Programming Contest (ISCPC) 2017

Problem Setter: Shahin ShamS