Write a small program to achieve the following:

Aliens from the planet of Jupiter have an extremely well-developed language. Recently they have introduced a special alphabet which consists of only 2 symbols. Now, they would like to develop a way to write down all the words they have in their language using this alphabet. They want to be able to decode sequences of words without breaks between them, so they would like to retain the following property: no word is the proper prefix of any other word. Knowing know how many words they have, that each word occurs equally often in every-day use, and knowing the effort required to write down each of the two symbols of the alphabet (the complexity of the first symbol and the second symbol need not to be equal!) help them to develop an encoding which minimizes the mean effort required to write down a word of the language.

First, 1≤t≤10000, the number of test cases. Each test case contains: 1≤a≤109, 1≤b≤109, 1≤n≤1012, meaning: the effort required for writing down the first symbol, the effort required for writing down the second symbol, and the number of words of the language, respectively.

For each testcase, output the total effort required to obtain all words in the optimal encoding.

Input:

2

2 1 3

1 1 16

Output:

7

64

Explanation

The optimal encoding for the first testcase is:

'0','10','11'.

The optimal encoding for the second testcase is:

'0000','0001',...,'1110','1111'.

It was up in a coding contest and my implementation took more time than permitted. I'm sure you guys can do better

**Problem**:Aliens from the planet of Jupiter have an extremely well-developed language. Recently they have introduced a special alphabet which consists of only 2 symbols. Now, they would like to develop a way to write down all the words they have in their language using this alphabet. They want to be able to decode sequences of words without breaks between them, so they would like to retain the following property: no word is the proper prefix of any other word. Knowing know how many words they have, that each word occurs equally often in every-day use, and knowing the effort required to write down each of the two symbols of the alphabet (the complexity of the first symbol and the second symbol need not to be equal!) help them to develop an encoding which minimizes the mean effort required to write down a word of the language.

**Input**First, 1≤t≤10000, the number of test cases. Each test case contains: 1≤a≤109, 1≤b≤109, 1≤n≤1012, meaning: the effort required for writing down the first symbol, the effort required for writing down the second symbol, and the number of words of the language, respectively.

**Output**For each testcase, output the total effort required to obtain all words in the optimal encoding.

**Example**Input:

2

2 1 3

1 1 16

Output:

7

64

Explanation

The optimal encoding for the first testcase is:

'0','10','11'.

The optimal encoding for the second testcase is:

'0000','0001',...,'1110','1111'.

It was up in a coding contest and my implementation took more time than permitted. I'm sure you guys can do better