Jem is famous for his laziness at school. He always leaves things to last minute. Now Jem has N problems in the assignment of "Advanced topics in algorithm" class to solved. The assignment is due tomorrow and as you may guess he hasn't touch any of the problems. Fortunately he got a plan as always.

The first step will be buying a pack of Red Bull and then to work as hard as he can. Here is how he is going to spend the remaining time:

Jem will not take a break until he finishes at least half of the remaining problems. Formally, if N is even then he will take he first break after finishing N / 2 problems. If N is odd then the break will be after he done (N + 1) / 2 problems. Each of his break will last for B minutes. Initially, he takes M minutes in solving a problem, after each break he will take twice more time in solving a problem, i.e. 2 * M minutes per problem after the first break.

Jem will start working soon and ask you to help him calculate how much time it will take until he finish the last problem!

-----Input-----

The first line contains a single integer T represents the number of test cases in the input.
Each line in the next T line contains three integers N, B and M represents a test case.

-----Output-----

For each test case output a single line containing an integer represent how much time Jem will need (in minutes).

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N, B, M ≤ 108

-----Example-----
Input:
2
9 1 2
123456 123456 123456

Output:
45
131351258112

-----Explanation-----

In the first test case, Jem will proceed as below:

- Initially, Jem has 9 problems to solve. since it is an odd number, Jem will finish the first (9 + 1) / 2 = 5 problems with speed of 2 minutes/problem.
- After that, Jem takes 1 minute break.
- Now he has 4 problems to solve, which is an even number, so Jem will solve the next 4 / 2 = 2 problems. his speed after the first break has now became 4 minutes/problem.

- Again, he takes a 1 minute break.
- he has now 2 problems left so he do one more problem in 8 minutes.
- He takes 1 minute break.
- he solves the last problem in 16 minutes.

So, Jem will need time = 5 × 2 + 1 + 2 × 4 + 1 + 8 + 1 + 16  = 45

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def calc(n,b,m):\n if(n==1):\n  return m\n if(n%2==0):\n  return m*n/2 + b + calc(n/2,b,m*2)\n else:\n  return m*(n+1)/2 + b + calc((n-1)/2,b,m*2)\n \nt=int(input());\nwhile (t!=0):\n t=t-1\n n,b,m = list(map(int, input().split()))\n print(calc(n,b,m))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13111