291. Fibonacci 2.0

Problem Statement:
Fibonacci sequence is a sequence of numbers where F(n) = F(n - 1) + F(n - 2) and the sequence starts with 0, and 1. As Fibonacci sequence is very old, we are going to invent a new one, Fibonacci 2.0 also known as Y(n).

Y(n) = Y(n - 1) + Y(n - 2) as well but this time this sequence doesn't have to start with 0 and 1 but can start with any two numbers A and B where 0  ≤  A  ≤  B  ≤  100.

We are interested in the Fibonacci 2.0 sequence which starts with A and B and Y(X) is the closest value to a given integer N. Since the answer is not unique, we are interested in the sequence with the smallest A. If the answer is not unique yet, we are interested in the sequence with the smallest B. If the answer is not unique yet, we are interested in the smallest X.

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  100,000). Followed by T test cases. Each test case will consist of a single line, containing integer N (1  ≤  N  ≤  1018).

Output Format:
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by a single space, followed by 3 integers separated by a single space representing A, B and X.

Sample Input:
3 10 20 30

Sample Output:
Case 1: 0 2 5 Case 2: 0 4 5 Case 3: 0 6 5

 Added by: ahmed_aly Added at: 2014-10-11 15:00:08 UTC Time Limit: 3 seconds Partial score: No Source: ACM Egyptian Collegiate Programming Contest 2014