Math is very favorite to Beak Sing Jo. He is a very brilliant student and always attentive to his studies. Ohani is a girl of his class. She always tries to be a friend of Beak Sing Jo. But Beak doesn’t like her at all. She is never serious for her study. But she always tries to take the attention of Beak.

So, one day Beak gave her a condition. If Ohani can solve a math, he will accept her friendship. He gave Ohani the following question.

You will be given an integer n. You will have to find an integer number X of n digits that satisfies the condition:

            X + 2 = reverse(2 * X)

Here reverse(x) means to arrange the digits of the number in the reverse order.

Ohani is very weak in mathematics. But she knows that you are a great programmer. So she told you to make a program for her which will solve the question.

Input

The first line of the input will be the number of test cases T where T <= 50. Next T lines will contain an integer n and n will always be less than 300001.

Output

You have to output the answer in the following format:

“Case y: x”

Where y is the case number and x is the desired n digit number.

Example

Input:
3
1
2
3

Output:
Case 1: 2
Case 2: 47
Case 3: 497

Problem Setter & Dataset: Raihat Zaman Neloy Dept. CSE, JU