You have cents at the beginning, and there is a bank that accepts time deposits of your cents.
The time is measured in years and the interest rate is all the time. That is, if you make a time deposit of cents for years (both and must be integers), then after years, you can get back cents from the bank, where is the largest integer that is less or equal to . If you make multiple deposits, the interest of each deposit will be calculated independently.
You want to find the best strategy to deposit your cents such that the amount of cents you will own is maximized after years.
输入格式
The first line is the number of test cases up to 120. For each test case, there are three integers , and (, , , ).
输出格式
For each test case, output the maximum number of cents you will own after years.
