N teams have come to participate in a competitive coding event called “Binary Battles”. It is a [single-elimination tournament] consisting of several rounds.

Note: It is known that N is a power of 2.

In one round, each team will be paired up with and compete against one of the other teams. If there are X teams before the start of a round, \frac{X}{2} matches are held simultaneously during the round between \frac{X}{2} pairs of teams. The winning team of each match will move on to the next round, while the losing team of each match will be eliminated. There are no ties involved. The next round will then take place in the same format between the remaining teams. The process will continue until only one team remains, which will be declared the overall winner.

The organizers want to find the total time the event will take to complete. It is given that each round spans A minutes, and that there is a break of B minutes between every two rounds (no break after the last round).

For example, consider a case when N = 4, A = 10 and B = 5. The first round will consist of two matches and will take 10 minutes to complete. Two teams move on to round 2 and the other two get eliminated. Then there is a break of 5 minutes. The two remaining teams compete in round 2, which lasts 10 more minutes. The team that wins is declared the overall winner. Thus the total time taken is 10 + 5 + 10 = 25 minutes.

Can you help the organizers determine how long the event will take to finish?

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases. Then the test cases follow.
- The first and only line of each test case contains three space-separated integers N, A and B respectively — the number of teams, the duration of each round and the length of the breaks between rounds.
    
------ Output Format ------ 

For each test case, output on a new line the time taken in minutes for the whole event to finish.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 2^{20}$
$1 ≤ A ≤ 100$
$1 ≤ B ≤ 100$
$N$ is a power of $2$.

----- Sample Input 1 ------ 
4
4 10 5
16 30 5
32 45 15
1024 23 9

----- Sample Output 1 ------ 
25
135
285
311
----- explanation 1 ------ 
Test case 1: As explained above, the total time the competition will take is $10 + 5 + 10 = 25$ minutes.

Test case 2: $4$ rounds will take place. The total time it will take is $30 + 5 + 30 + 5 + 30 + 5 + 30 = 135$ minutes.

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
T = int(input())
for i in range(T):
	(x, y, z) = input().split()
	(x, y, z) = (int(x), int(y), int(z))
	t = 0
	while x > 1:
		x /= 2
		t += y
		if x != 1:
			t += z
	print(t)


for I in range(int(input())):
	(a, b, c) = map(int, input().split())
	f = -1
	while a:
		a //= 2
		f += 1
	k = f * b + (f - 1) * c
	print(k)


for i in range(int(input())):
	c = 0
	(n, a, b) = [int(x) for x in input().split()]
	while n != 1:
		n = n // 2
		c = c + 1
	print(c * a + (c - 1) * b)
	c = 0


t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	i = 1
	while n > 0:
		n = n - 2 ** i
		i += 1
	x = a * (i - 1)
	y = b * (i - 2)
	print(x + y)


T = int(input())
for i in range(T):
	(N, A, B) = map(int, input().split())
	power = 0
	while N > 1:
		power += 1
		N /= 2
	print(power * A + (power - 1) * B)


t = int(input())
i = 0
for i in range(t):
	(n, a, b) = map(int, input().split())
	c = 0
	while n > 1:
		n = n // 2
		c = c + 1
	d = a * c + (c - 1) * b
	print(d)


for i in range(int(input())):
	(x, y, z) = map(int, input().split())
	j = 0
	while j < j + 1:
		if x == 1:
			y = y * j
			z = z * (j - 1)
			break
		else:
			x = x // 2
			j += 1
	print(y + z)


for _ in range(int(input())):
	(N, A, B) = map(int, input().split())
	(C, rounds) = (1, 0)
	while C < N:
		C = C * 2
		rounds += 1
	print(rounds * A + (rounds - 1) * B)


T = int(input())
for i in range(0, T):
	(N, A, B) = map(int, input().split())
	t = 0
	count = 0
	x = N
	while N > 1:
		count = count + 1
		N = N / 2
	print(count * A + (count - 1) * B)


for i in range(int(input())):
	(x, y, z) = map(int, input().split())
	p = 0
	while x > 1:
		p += 1
		x = x / 2
	k = p * y + (p - 1) * z
	print(k)


T = int(input())
for i in range(T):
	(a, b, c) = map(int, input().split())
	rounds = 0
	while a != 1:
		a = a / 2
		rounds = rounds + 1
	print(b * rounds + c * (rounds - 1))


import math
tc = int(input())
for i in range(tc):
	(n, a, b) = map(int, input().split())
	log = math.log(n, 2)
	total_time = a * log + b * (log - 1)
	print(int(total_time))


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	f = -1
	while n:
		n = n // 2
		f += 1
		k = f * a + (f - 1) * b
	print(k)


import math
for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	x = math.log2(n)
	y = int(a * x + b * (x - 1))
	print(y)


for i in range(int(input())):
	(n, x, y) = map(int, input().split())
	count = 0
	while n > 1:
		n = n // 2
		count = count + 1
	print(count * x + (count - 1) * y)


t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	temp = n // 2
	count = 1
	while temp != 1:
		temp = temp // 2
		count += 1
	time = count * a + (count - 1) * b
	print(time)


import math as m
t = int(input())
for i in range(t):
	r = 0
	q = -1
	(a, b, c) = map(int, input().split())
	while a != 0:
		q += 1
		a = a // 2
	for i in range(q):
		r += b + c
	print(r - c)


import math
for i in range(int(input())):
	(x, y, z) = map(int, input().split())
	for i in range(1, 21):
		if pow(2, i) == x:
			break
	print(y * i + (i - 1) * z)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	d = bin(n)
	t = d.count('0') - 1
	print(t * a + b * (t - 1))


for i in range(int(input())):
	(teams, c_time, b_time) = map(int, input().split())
	rounds = 0
	while teams > 1:
		rounds += 1
		teams /= 2
	tot_time = rounds * c_time + (rounds - 1) * b_time
	print(tot_time)


import math
for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	k = 1
	while n // 2 != 1:
		n = n // 2
		k += 1
	print(k * a + (k - 1) * b)


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	p = 0
	while n > 1:
		p = p + 1
		n = int(n / 2)
	print(p * a + (p - 1) * b)


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	p = 0
	while True:
		if n % 2 == 0:
			p = p + 1
		else:
			break
		n = int(n / 2)
	print(p * a + (p - 1) * b)


import math
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	print(int(math.log(a, 2) * (b + c) - c))


import math
for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	for j in range(a):
		d = 2 ** j
		if a == d:
			break
		else:
			j = j + 1
	ans1 = b * j
	ans2 = ans1 + c * (j - 1)
	print(ans2)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	c = 0
	for i in range(n):
		n = n // 2
		c += 1
		if n == 1:
			break
	print(c * (a + b) - b)


import math
for j in range(int(input())):
	lst = list(map(int, input().strip().split()))
	print(round(math.log(lst[0], 2)) * (lst[1] + lst[2]) - lst[2])


import math
t = int(input())
for i in range(t):
	(N, A, B) = map(int, input().split())
	N = int(math.log(N, 2))
	print(N * A + (N - 1) * B)


t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	z = -1
	while n:
		n //= 2
		z += 1
	print(z * a + (z - 1) * b)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	C = 0
	while a != 1:
		a = a // 2
		C += 1
	bre = C - 1
	time = C * b + bre * c
	print(time)


import math
T = int(input())
for i in range(T):
	(N, A, B) = map(int, input().split())
	no_of_rounds = int(math.log2(N))
	rounds = 1
	time = 0
	while rounds:
		if rounds == no_of_rounds:
			time += A
			break
		else:
			time += A + B
			rounds += 1
	print(time)


def num_rounds(n):
	if n == 1:
		return 0
	else:
		return 1 + num_rounds(n // 2)
T = int(input())
for i in range(T):
	(N, A, B) = map(int, input().split())
	c = num_rounds(N)
	print(A * c + B * (c - 1))


def solve():
	from math import log2 as lg
	(n, a, b) = map(int, input().split())
	n = lg(n)
	n = int(n)
	time = n * a + (n - 1) * b
	return time

def main():
	for _ in range(int(input())):
		print(solve())
main()


import math
for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	a = math.log(a, 2)
	a = int(a)
	ans = a * b + (a - 1) * c
	print(ans)


import math
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	val = math.log(n, 2)
	print(int(val * a + (val - 1) * b))


t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	f = -1
	while n:
		n //= 2
		f += 1
	k = f * a + (f - 1) * b
	print(k)


T = int(input())
for _ in range(T):
	(N, A, B) = map(int, input().split())
	c = 0
	for i in range(N):
		N = N // 2
		c += 1
		if N == 1:
			break
	print(c * (A + B) - B)


def code():
	cases = int(input())
	for i in range(cases):
		(N, A, B) = map(int, input().split(' '))
		cur = N
		time = 0
		round_num = 0
		while cur != 1:
			round_num += 1
			cur -= cur / 2
			if round_num % 2 == 0:
				time += B
			time += A
		print(round_num * A + (round_num - 1) * B)
code()


import math
for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	temp = int(math.log2(n))
	print(temp * a + (temp - 1) * b)


t = int(input())
a = []
for i in range(t):
	a.append(input())

def ans(n, c, b):
	p = 0
	while True:
		if n == 1:
			break
		else:
			n //= 2
			p += 1
	return c * p + b * (p - 1)
for i in a:
	i = i.split(' ')
	print(ans(int(i[0]), int(i[1]), int(i[2])))


def power(n):
	count = 0
	while n > 1:
		n //= 2
		count += 1
	return count
for i in range(int(input())):
	(N, A, B) = map(int, input().split())
	q = power(N)
	print(q * A + B * (q - 1))


def power(n):
	count = 0
	while n > 1:
		n //= 2
		count += 1
	return count
for _ in range(int(input())):
	(N, A, B) = map(int, input().split())
	sq = power(N)
	print(sq * A + B * (sq - 1))


import math
for _ in range(int(input())):
	(x, y, z) = map(int, input().split())
	print(int((math.log(x, 2) - 1) * (y + z) + y))