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 13⁰ = 1 and 13³ = 2197) and those that are a sum of unique powers of 13 (such as 170 = 13⁰ + 13² or 182 = 13¹ + 13², but not 26 = 13¹ + 13¹). 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 N^th 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 N^th 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