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 grownup: • Every morning, the height of each lunar tree increases by 1. • 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: • 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). • Everyevening,pouraglassofmagicwaterontoaseedthathasjustbeenplantedthatafternoon, 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. 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.
2/2 Day Morning(heights) Noon(seed Afternoon(action) count) Evening(tree watered) Seed Seed Seed Tree of Height 2 Tree of Height 4 Tree of Height 5 1 (No tree) 1 2 2 1 3 3,2 2 4 4,3,2 3 5 5,4,4 4 6 6,6,5 4 Plant 1 seed No action Plant 1 seed No action No action No action You see, after 6 days (6 glasses of magic water were poured), we’ll have three trees: 7, 7, 7 Sample Input 2 233 3 4 14 Sample Output Case 1: 6 Case 2: 99