Problem D
Lunar Forest
Input: Standard Input

Output: Standard Output

Linda is a lovely girl living in the forest. Every morning she wakes up early, plays with animals and enjoys the beautiful landscape. She loves the forest very much.

One day, she found an exceptional shining little thing on the ground. It was a seed! Linda loved it so much that she immediately took it home.

That night, Linda had a strange dream. She was told that the seed was from a lunar tree. If she plants the seed with care, a beautiful lunar tree can grow up in the forest! What's more, lunar trees will produce seeds. She can grow a tree, take seeds, plant seeds, then grow another tree... Then there will be more and more beautiful lunar trees. What a good idea!

Here is how lunar trees are grown up:

l Every morning, the height of each lunar tree increases by 1.

l Every tree has two harvest point HP1 and HP2 For each harvest point, the first day that its height equals or exceeds the height of harvest point, it produces a seed, in the noon. It is possible that the tree produces two seeds at the same time, but a tree can produce at most two seeds in total.

Here is her plan:

l Every afternoon, plant zero or more seeds. Those lunar seeds will become lunar tree of height 1 the next morning. (if nothing else is done).

l Every evening, pour a glass of magic water onto a seed that has just been planted that afternoon, or onto a lunar tree. The magic water makes the lunar tree grow 1 extra height unit. For seeds, they'll be lunar trees of height 2 the next morning, for trees, their heights will increase by 2, not 1. She cannot pour onto two or more seeds or trees, and she cannot pour onto no seeds or trees.

Linda wished that there would eventually be, by her hand, a lunar forest of m trees, with all the trees of the same height. How fast can this be?

Input

The first line contains a single integer t(1<=t<=25), the number of test cases. Each test case is a single line containing 3 integers: HP1, HP2 and m(2<=HP1<HP2<=8, 2<=m<=16)

Output

For each case, print the case number, followed by the minimum number of days required.

Sample Input Output for Sample Input

2 3 3

3 4 14

Case 1: 6

Case 2: 99

Problem setter: Rujia Liu

Special Thanks: Derek Kisman

Explanation of Sample 1

Here is a table. We give tree heights in the morning, number of seeds available in the noon, how many seeds are planted in the afternoon, and which tree (or seed) is poured magic water. Since trees are identical, we use height to denote a tree.

Day	Morning(heights)	Noon(seed count)	Afternoon(action)	Evening(tree watered)
1	(No tree)	1	Plant 1 seed	Seed
2	2	1	No action	Seed
3	3, 2	2	Plant 1 seed	Seed
4	4, 3, 2	3	No action	Tree of Height 2
5	5, 4, 4	4	No action	Tree of Height 4
6	6, 6, 5	4	No action	Tree of Height 5

You see, after 6 days (6 glasses of magic water were poured), we'll have three trees: 7, 7, 7