Chef has an integer N. He repeats the following operation until N becomes 1.

- Chef chooses an integer X such that X > 1 and X is a divisor of N and then divides N by X (the new value of N becomes N/X). If X is even, Chef gets A points otherwise he gets B points

Can you find the maximum points Chef can get if he performs the operations optimally?

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains of a single line of input containing three integers N, A, B.

------ Output Format ------ 

For each testcase, output in a single line the maximum points Chef can get.

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

$1 ≤ T ≤ 2\cdot10^{3}$
$2 ≤ N ≤ 10^{9}$
$-10^{3}≤ A, B ≤ 10^{3}$

----- Sample Input 1 ------ 
4
10 2 3
15 5 -2
12 2 3
8 -1 0

----- Sample Output 1 ------ 
5
-2
7
-1

----- explanation 1 ------ 
Test case $1$: First Chef divides $N = 10$ by $2$ and gets $2$ points and then divides by $5$ and thus gets $3$ points. Hence Chef gets a total of $2 + 3 = 5$ points.

Test case $2$: Chef divides $N$ by $15$. Hence he gets $-2$ points.

Difficulty: MEDIUM_HARD
Tags: Number theory

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
def snek(n):
	even = 0
	odd = 0
	while n % 2 == 0:
		n //= 2
		even += 1
	for j in range(3, int(n ** 0.5) + 1, 2):
		if n % j == 0:
			while n % j == 0:
				n //= j
				odd += 1
	if n != 1:
		odd += 1
	return [even, odd]
t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	ans = snek(n)
	if a < 0 and b < 0:
		if n % 2 == 0:
			print(a)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if ans[0] > 0:
			print(ans[1] * b + a)
		else:
			print(ans[1] * b)
	elif a >= 0 and b < 0:
		if ans[0] > 0:
			print(ans[0] * a)
		else:
			print(b)
	else:
		print(ans[0] * a + ans[1] * b)


def factors(n):
	cnt_even = 0
	cnt_odd = 0
	while n % 2 == 0:
		n = n // 2
		cnt_even += 1
	for j in range(3, int(n ** 0.5) + 1, 2):
		if n % j == 0:
			while n % j == 0:
				n = n // j
				cnt_odd += 1
	if n != 1:
		cnt_odd += 1
	return [cnt_even, cnt_odd]
for i in range(int(input())):
	(n, a, b) = [int(x) for x in input().split()]
	ans = factors(n)
	if a < 0 and b < 0:
		if n % 2 == 0:
			print(a)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if ans[0] > 0:
			print(ans[1] * b + a)
		else:
			print(ans[1] * b)
	elif a >= 0 and b < 0:
		if ans[0] > 0:
			print(ans[0] * a)
		else:
			print(b)
	else:
		print(ans[0] * a + ans[1] * b)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	odd = 0
	even = 0
	while n % 2 == 0:
		even += 1
		n = n // 2
	q = n
	i = 3
	while i * i <= n and q > 1:
		while q % i == 0:
			odd += 1
			q = q // i
		i += 2
	if q > 1:
		odd += 1
	c = 0
	if b <= 0 and even > 0:
		if a > 0:
			c += a * even
		else:
			c += a
	else:
		if even > 0:
			if a > 0:
				c += a * even
			else:
				c += a
		if odd > 0:
			if b > 0:
				c += b * odd
			else:
				c += b
	print(c)


import math
t = int(input())
for _ in range(t):
	(n, a, b) = [int(i) for i in input().split()]
	even = 0
	odd = 0
	while n % 2 == 0:
		even += 1
		n //= 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			odd += 1
			n //= i
	if n > 2:
		odd += 1
	ans = 0
	if a >= 0 and b >= 0:
		ans = even * a + odd * b
	elif a <= 0 and b <= 0:
		if even:
			ans = a
		else:
			ans = b
	elif a >= 0 and b <= 0:
		if even:
			ans = even * a
		else:
			ans = b
	elif a <= 0 and b >= 0:
		if even:
			ans = a + odd * b
		else:
			ans = odd * b
	print(ans)


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
lx = lambda x: map(int, input().split(x))
yy = lambda : print('YES')
nn = lambda : print('NO')
from math import log10, log2, ceil, factorial as fac, gcd, inf, sqrt, log
from bisect import bisect_right as br, bisect_left as bl, insort
from collections import Counter
mod = 10 ** 9 + 7

def Nprime(n):
	if n == 2 or n == 3:
		return 0
	if n == 1:
		return 1
	i = 2
	while i * i <= n:
		if n % i == 0:
			return 1
		i += 1
	return 0

def g(n):
	i = 2
	(od, ev) = (0, 0)
	x = n
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
				if i % 2:
					od += 1
				else:
					ev += 1
		i += 1
	if n > 1:
		if n % 2:
			od += 1
		else:
			ev += 1
	return (od, ev)
for _ in range(t()):
	(n, a, b) = ll()
	ans = 0
	(od, ev) = g(n)
	if a >= 0 and b >= 0:
		ans = a * ev + b * od
	if a >= 0 and b < 0:
		ans = a * ev if n % 2 == 0 else b
	if a < 0 and b >= 0:
		ans = b * od + (a if ev > 0 else 0)
	if a < 0 and b < 0:
		ans = a if ev else b
	print(ans)


import collections
from math import log2
t = int(input())
for _ in range(0, t):
	(n, a, b) = map(int, input().split())
	points = 0
	counta = 0
	countb = 0
	while n % 2 == 0:
		counta += 1
		n = n // 2
	j = 3
	while j * j <= n:
		while n % j == 0:
			n = n // j
			countb += 1
		j += 2
	if n > 1:
		countb += 1
	if a <= 0 and b <= 0:
		if counta > 0:
			points = a
		else:
			points = b
	elif a <= 0 and b >= 0:
		if counta > 0:
			points += a
		points += countb * b
	elif a >= 0 and b <= 0:
		if counta > 0:
			points += counta * a
		else:
			points += b
	else:
		points += counta * a + countb * b
	print(points)


from math import sqrt
leastPrime = [0] * 100001
leastPrime[1] = 1
for i in range(2, 100001, 1):
	if leastPrime[i] == 0:
		j = i
		while j <= 100000:
			if leastPrime[j] == 0:
				leastPrime[j] = i
			j += i

def leastPrimeDivisor(n):
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return i
	return n
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	ans = 0
	on = n
	if a >= 0:
		while n % 2 == 0:
			n //= 2
			ans += a
		if b >= 0:
			while n != 1:
				if n > 100000:
					n //= leastPrimeDivisor(n)
				else:
					n //= leastPrime[n]
				ans += b
		elif n != 1:
			if on % 2 == 1:
				ans += b
	elif a < 0 and b > 0:
		if n % 2 == 0:
			ans += a
			while n % 2 == 0:
				n //= 2
		while n != 1:
			if n > 100000:
				n //= leastPrimeDivisor(n)
			else:
				n //= leastPrime[n]
			ans += b
	elif a < 0 and b <= 0:
		if n != 1:
			if n % 2 == 0:
				ans += a
			else:
				ans += b
	print(ans)


import math

def primer(n):
	eve = 0
	odd = 0
	while n % 2 == 0:
		eve += 1
		n = n // 2
	truth = False
	for i in range(3, int(math.sqrt(n) + 1), 2):
		while n % i == 0:
			truth = False
			odd += 1
			n = n // i
			if n == 1:
				break
	if n > 2 and truth:
		primer(n)
	elif n == 1:
		uyt = 0
	else:
		odd += 1
	x = [eve, odd]
	return x
n1 = int(input())
i = 0
while i < n1:
	(n, a, b) = input().split()
	n = int(n)
	a = int(a)
	b = int(b)
	if a == 0 and b == 0:
		print(0)
	elif a >= 0 and b >= 0:
		x = primer(n)
		ans = a * x[0] + b * x[1]
		print(ans)
	elif a <= 0 and b >= 0:
		x = primer(n)
		if x[0] > 0:
			ans = a + b * x[1]
		else:
			ans = b * x[1]
		print(ans)
	else:
		x = primer(n)
		if x[0] == 0 and a > 0 and (b < 0):
			print(b)
		elif x[0] == 0 and a < 0 and (b < 0):
			print(b)
		elif a < 0 and b < 0:
			print(a)
		elif a == 0 and b < 0:
			if x[0] == 0:
				print(b)
			else:
				print(0)
		else:
			print(int(x[0] * a))
	i += 1


import math

def GetPrimeFactors(num):
	even = 0
	odd = 0
	while num % 2 == 0:
		even += 1
		num = num // 2
	for i in range(3, int(math.sqrt(num)) + 1, 2):
		while num % i == 0:
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
			num = num // i
	if num > 2:
		if num % 2 == 0:
			even += 1
		else:
			odd += 1
	return (even, odd)
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	(even, odd) = GetPrimeFactors(n)
	if a >= 0 and b >= 0:
		ans = a * even + b * odd
	elif a >= 0 and b < 0:
		if even > 0:
			ans = a * even
		else:
			ans = b
	elif a < 0 and b >= 0:
		if even > 0:
			ans = a + b * odd
		else:
			ans = b * odd
	elif n % 2 == 0:
		ans = a
	else:
		ans = b
	print(ans)


from math import sqrt

def fact(n):
	o = e = 0
	while n % 2 == 0:
		e += 1
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while not n % i:
			if i & 1:
				o += 1
			else:
				e += 1
			n //= i
	if n > 2:
		if n & 1:
			o += 1
		else:
			e += 1
	return (e, o)
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	c = 0
	(e, o) = fact(n)
	if a >= 0 and b >= 0:
		print(e * a + o * b)
	elif a >= 0 and b < 0:
		if n & 1 == 0:
			print(e * a)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if e != 0:
			print(a + o * b)
		else:
			print(o * b)
	elif n & 1:
		print(b)
	else:
		print(a)


import math

def pf(n):
	e = 0
	o = 0
	x = 3
	while n % 2 == 0:
		e += 1
		n //= 2
	for x in range(3, int(math.sqrt(n)) + 1, 2):
		while n % x == 0:
			n /= x
			o += 1
	if n > 2:
		o += 1
	return (e, o)
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	(e, o) = pf(n)
	if a >= 0 and b >= 0:
		print(e * a + o * b)
	elif a >= 0 and b < 0:
		if e:
			print(e * a)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if e:
			print(a + o * b)
		else:
			print(o * b)
	elif e == 0:
		print(b)
	else:
		print(a)


import math

def cal(n):
	(ec, oc) = (0, 0)
	while n % 2 == 0:
		ec += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i % 2 == 0:
				ec += 1
			else:
				oc += 1
			n = n / i
	if n > 2:
		oc += 1
	return [ec, oc]
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	c = 0
	(e, o) = cal(n)
	if a >= 0 and b >= 0:
		print(e * a + o * b)
	elif a >= 0 and b < 0:
		if n & 1 == 0:
			print(e * a)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if e != 0:
			print(a + o * b)
		else:
			print(o * b)
	elif n & 1:
		print(b)
	else:
		print(a)


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	i = 2
	(even_sum, odd_sum) = (0, 0)
	while i * i <= n:
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				cnt += 1
				n /= i
			if i % 2 == 0:
				even_sum += cnt
			else:
				odd_sum += cnt
		i += 1
	if n > 1:
		if n % 2 == 0:
			even_sum += 1
		else:
			odd_sum += 1
	ans = 0
	if a >= 0:
		ans += a * even_sum
	elif even_sum > 0:
		ans += a
	if b >= 0:
		ans += b * odd_sum
	elif even_sum == 0 and odd_sum > 0:
		ans += b
	print(ans)


import math
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	(odd, even) = (0, 0)
	while n % 2 == 0:
		n = n // 2
		even += 1
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			n = n // i
			odd += 1
	if n > 2:
		odd += 1
	if a >= 0 and b >= 0:
		sol = even * a + odd * b
	elif a >= 0 and b < 0:
		sol = even * a if even else b
	elif a < 0 and b >= 0:
		sol = a + odd * b if even else odd * b
	elif a < 0 and b < 0:
		sol = a if even else b
	print(sol)


import math

def even(n):
	p = 0
	while n % 2 == 0:
		p += 1
		n //= 2
	return p

def fact(n):
	p = 0
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			p += 1
			n //= i
		while n % (n / i) == 0:
			p += 1
			n //= n / i
	if n > 2:
		p += 1
	return p
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a >= 0 and b >= 0:
		print(even(n) * a + fact(n / 2 ** even(n)) * b)
	elif a >= 0 and b < 0:
		if n % 2 == 0:
			print(even(n) * a)
		else:
			print(even(n) * a + b)
	elif a < 0 and b >= 0:
		if n % 2 == 0:
			print(fact(n / 2 ** even(n)) * b + a)
		else:
			print(fact(n / 2 ** even(n)) * b)
	elif n % 2 == 0:
		print(a)
	else:
		print(b)


def prime_fac(n):
	even = 0
	odd = 0
	for i in range(2, n):
		if i * i > n:
			break
		while n % i == 0:
			n /= i
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
	if n != 1:
		if n % 2 == 0:
			even += 1
		else:
			odd += 1
	return (even, odd)
for t in range(int(input())):
	(n, a, b) = map(int, input().split())
	(even, odd) = prime_fac(n)
	if a >= 0 and b >= 0:
		print(a * even + b * odd)
	elif a >= 0 and b < 0:
		if even > 0:
			print(a * even)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if even > 0:
			print(a + b * odd)
		else:
			print(b * odd)
	elif a < 0 and b < 0:
		if even > 0:
			print(a)
		else:
			print(b)


import math
num = int(input())
for i in range(num):
	count = 0
	(n, a, b) = map(int, input().split())
	odd = 0
	even = 0
	for t in range(2, n):
		if t * t > n:
			break
		else:
			while n % t == 0:
				n = n / t
				if t % 2 == 0:
					even += 1
				else:
					odd += 1
	if n > 1:
		if n % 2 == 0:
			even += 1
		else:
			odd += 1
	if a >= 0 and b >= 0:
		print(a * even + b * odd)
	elif a >= 0 and b < 0:
		if even > 0:
			print(a * even)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if even > 0:
			print(a + b * odd)
		else:
			print(b * odd)
	elif a < 0 and b < 0:
		if even > 0:
			print(a)
		else:
			print(b)


from collections import Counter

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
for test in range(int(input())):
	(n, a, b) = list(map(int, input().split()))
	fac = prime_factors(n)
	count = dict(Counter(fac))
	ans = 0
	if count.get(2, -1) == -1:
		count[2] = 0
	if a >= 0 and b >= 0:
		ans += count[2] * a
		del count[2]
		rest = sum(count.values())
		ans += rest * b
	elif a >= 0 and b < 0:
		ans += count[2] * a if n % 2 == 0 else b
	elif a < 0 and b >= 0:
		if n % 2 == 0:
			ans += a
		del count[2]
		rest = sum(count.values())
		ans += rest * b
	else:
		ans += a if n % 2 == 0 else b
	print(ans)


for _ in range(int(input())):
	(N, A, B) = map(int, input().split())
	even = 0
	odd = 0
	i = 2
	while i * i <= N:
		while N % i == 0:
			N /= i
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
		i += 1
	if N > 1:
		if N % 2 == 0:
			even += 1
		else:
			odd += 1
	res = 0
	if A >= 0 and B >= 0:
		res = A * even + B * odd
	if A >= 0 and B < 0:
		if even > 0:
			res = even * A
		else:
			res = B
	if A < 0 and B >= 0:
		res = odd * B + (A if even > 0 else 0)
	if A < 0 and B < 0:
		res = A if even > 0 else B
	print(res)


import math
for tc in range(int(input())):
	ls = list(map(int, input().split()))
	(N, A, B) = (ls[0], ls[1], ls[2])
	even = odd = 0
	fiz = N
	while fiz % 2 == 0:
		even += 1
		fiz >>= 1
	for x in range(3, int(math.sqrt(fiz)) + 1, 2):
		if fiz % x == 0:
			while fiz > 1 and fiz % x == 0:
				fiz //= x
				odd += 1
			if fiz == 1:
				break
		if fiz == 1:
			break
	if fiz > 1:
		if fiz % 2 == 0:
			even += 1
		else:
			odd += 1
	ans = 0
	if A >= 0 and B >= 0:
		ans = even * A + odd * B
	elif A < 0 and B >= 0:
		if even > 0:
			ans = odd * B + A
		else:
			ans = odd * B
	elif A >= 0 and B < 0:
		if even > 0:
			ans = even * A
		else:
			ans = B
	elif even:
		ans = A
	else:
		ans = B
	print(ans)


from math import sqrt
for tc in range(int(input())):
	ls = list(map(int, input().split()))
	(N, A, B) = (ls[0], ls[1], ls[2])
	even = odd = 0
	while N % 2 == 0:
		even += 1
		N //= 2
	for i in range(3, int(sqrt(N)) + 1, 2):
		while not N % i:
			if i & 1:
				odd += 1
			else:
				even += 1
			N //= i
	if N > 2:
		if N & 1:
			odd += 1
		else:
			even += 1
	ans = 0
	if A >= 0 and B >= 0:
		ans = even * A + odd * B
	elif A < 0 and B >= 0:
		if even > 0:
			ans = odd * B + A
		else:
			ans = odd * B
	elif A >= 0 and B < 0:
		if even > 0:
			ans = even * A
		else:
			ans = B
	elif even:
		ans = A
	else:
		ans = B
	print(ans)


import sys
from math import cos, pi, ceil, pi, tan, floor, gcd, sqrt, log2, factorial, log10
from collections import Counter
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase
from statistics import mean, median, mode
from bisect import *
alpha = ascii_lowercase
beta = ascii_uppercase

def nextPowerOf2(n):
	p = 1
	if n and (not n & n - 1):
		return n
	while p < n:
		p <<= 1
	return p

def get_Divisors(n):
	arr = []
	i = 1
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				arr.append(i)
			else:
				arr.append(i)
				arr.append(n // i)
		i = i + 1
	return arr

def isprime(n):
	if n == 1:
		return 0
	i = 2
	while i * i <= n:
		if n % i == 0:
			return 0
		i += 1
	return 1

def Sieve(n):
	prime = [True for i in range(n + 1)]
	prime[0] = False
	prime[1] = False
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def create_matrix(n, m):
	mat = [[] for i in range(n)]
	for i in range(n):
		for j in range(m):
			mat[i].append(0)
	return mat

def main():
	for ttt in range(int(input())):
		(n, a, b) = map(int, input().split())
		nn = n
		arr = []
		while n % 2 == 0:
			arr.append(2)
			n = n // 2
		for i in range(3, int(sqrt(n)) + 1, 2):
			while n % i == 0:
				arr.append(i)
				n = n // i
		if n > 2:
			arr.append(n)
		odd = 0
		even = 0
		for i in arr:
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
		if a >= 0 and b >= 0:
			print(a * even + b * odd)
		elif a >= 0 and b < 0:
			if even > 0:
				print(even * a)
			else:
				print(b)
		elif a < 0 and b >= 0:
			f = 0
			if even > 0:
				f = 1
			print(b * odd + f * a)
		elif a < 0 and b < 0:
			if nn % 2 == 0:
				print(a)
			else:
				print(b)
main()


def primeFactors(n):
	i = 2
	L = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			L.append(i)
	if n >= 1:
		L.append(n)
	return L
for _ in range(int(input())):
	(N, A, B) = map(int, input().split())
	even = []
	odd = []
	for i in primeFactors(N):
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	(x, y) = (len(even), len(odd))
	if A >= 0 and B >= 0:
		print(A * x + B * y)
	elif A <= 0 and B >= 0:
		if x > 0:
			print(A + B * y)
		else:
			print(B * y)
	elif A >= 0 and B <= 0:
		if x == 0 and y > 0:
			print(B)
		elif x > 0 and y == 0:
			print(A * x)
		elif x > 0 and y > 0:
			print(A * x)
		else:
			print(0)
	elif x > 0 and y > 0:
		print(A)
	elif x > 0 and y == 0:
		print(A)
	elif x == 0 and y > 0:
		print(B)
	else:
		print(0)


import math

def primeFactors(n, ec, oc):
	while n % 2 == 0:
		ec += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i % 2 == 0:
				ec += 1
			else:
				oc += 1
			n = n / i
	if n > 2:
		oc += 1
	return [ec, oc]
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	odd = 0
	even = 0
	(even, odd) = primeFactors(n, even, odd)
	if a >= 0 and b >= 0:
		print(even * a + odd * b)
	elif a >= 0 and b < 0:
		if even > 0:
			print(a * even)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if even == 0:
			print(b * odd)
		else:
			print(b * odd + a)
	elif n % 2 == 0:
		print(a)
	else:
		print(b)


import math
t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	d = a
	e = 0
	o = 0
	while a % 2 == 0:
		e += 1
		a //= 2
	for j in range(3, int(math.sqrt(a)) + 1, 2):
		while a % j == 0:
			o += 1
			a //= j
	if a > 1:
		o += 1
	if b >= 0 and c >= 0:
		print(b * e + c * o)
	elif b >= 0 and c <= 0:
		if d % 2 == 0:
			print(b * e)
		elif b * e + c * o > c:
			print(b * e + c * o)
		else:
			print(c)
	elif b <= 0 and c >= 0:
		if d % 2 == 0:
			print(b + c * o)
		else:
			print(c * o)
	elif b <= 0 and c <= 0:
		if d % 2 == 0:
			print(b)
		else:
			print(c)


t = int(input())
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
for tt in range(t):
	(n, a, b) = map(int, input().split())
	(odd, even) = (0, 0)
	temp = n
	while temp % 2 == 0:
		even += 1
		temp /= 2
	i = 3
	while i * i <= temp:
		if temp % i == 0:
			while temp % i == 0:
				temp /= i
				odd += 1
		i += 1
	if temp != 1:
		odd += 1
	result = 0
	if n % 2 != 0:
		result = max(b, odd * b)
	elif (a >= 0) & (b >= 0):
		result += even * a
		result += odd * b
	elif (a >= 0) & (b <= 0):
		result = even * a
	elif (a <= 0) & (b >= 0):
		result = odd * b + a
	else:
		result = a
	print(result)


from math import sqrt

def primeFactors(n):
	res = []
	for i in range(2, int(sqrt(n)) + 1):
		while n % i == 0:
			res.append(i)
			n //= i
	if n > 1:
		res.append(n)
	return res
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	prime = primeFactors(n)
	(even, odd) = (0, 0)
	l = len(prime)
	for i in range(l):
		if prime[i] & 1:
			odd += 1
		else:
			even += 1
	if a < 0 and b < 0:
		if n & 1:
			print(b)
		else:
			print(a)
	elif a >= 0 and b >= 0:
		ans = a * even + b * odd
		print(ans)
	elif a < 0 and b >= 0:
		if even > 0:
			ans = b * odd + a
		else:
			ans = b * odd
		print(ans)
	elif a >= 0 and b < 0:
		if even > 0:
			ans = a * even
		else:
			ans = b
		print(ans)


import math
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	(even, odd) = (0, 0)
	i = 2
	while i * i <= n:
		if n % i == 0:
			count = 0
			while n % i == 0:
				count += 1
				n /= i
			if i % 2 == 0:
				even += count
			else:
				odd += count
		i += 1
	if n > 1:
		if n % 2 == 0:
			even += 1
		else:
			odd += 1
	ans = 0
	if a >= 0 and b >= 0:
		ans = even * a + odd * b
	if a >= 0 and b < 0:
		ans = even * a if even > 0 else b
	if a < 0 and b >= 0:
		ans = odd * b + (a if even > 0 else 0)
	if a < 0 and b < 0:
		ans = a if even else b
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = [int(x) for x in input().split()]
	c1 = 0
	c2 = 0
	while n[0] % 2 == 0:
		c1 += 1
		n[0] /= 2
	for i in range(3, int(math.sqrt(n[0])) + 1, 2):
		while n[0] % i == 0:
			c2 += 1
			n[0] /= i
	if n[0] > 2:
		c2 += 1
	if n[1] >= 0 and n[2] >= 0:
		print(n[1] * c1 + n[2] * c2)
	elif n[1] >= 0 and n[2] < 0:
		if c1 != 0:
			print(n[1] * c1)
		else:
			print(n[2])
	elif n[1] < 0 and n[2] >= 0:
		if c1 != 0:
			print(n[1] + n[2] * c2)
		else:
			print(n[2] * c2)
	elif n[1] < 0 and n[2] < 0:
		if c1 > 0:
			print(n[1])
		else:
			print(n[2])


def prime(n):
	(l, m) = (0, 0)
	while n % 2 == 0:
		n /= 2
		l += 1
	i = 3
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n /= i
				m += 1
		i += 1
	if n != 1:
		m += 1
	return (l, m)

def func():
	(n, a, b) = map(int, input().split())
	(ec, oc) = prime(n)
	if a >= 0 and b >= 0:
		return ec * a + oc * b
	elif a >= 0 and b <= 0:
		if ec:
			return ec * a
		else:
			return b
	elif a <= 0 and b >= 0:
		if ec:
			return a + oc * b
		else:
			return oc * b
	elif ec:
		return a
	else:
		return b
t = int(input())
for i in range(t):
	print(func())


import heapq
import math
import sys
import collections
import bisect
import time
import random
import itertools
import string
from collections import Counter, defaultdict

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def primeFactors(n):
	res = []
	while n % 2 == 0:
		res.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			res.append(i)
			n = n // i
	if n > 2:
		res.append(n)
	return res
for t in range(int(input())):
	(n, a, b) = get_ints()
	pf = primeFactors(n)
	even = 0
	odd = 0
	for i in pf:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	ans = 0
	if a >= 0 and b >= 0:
		ans += even * a
		ans += odd * b
	elif a >= 0 and b <= 0:
		ans += even * a
		if even == 0:
			ans += b
	elif a <= 0 and b >= 0:
		ans += odd * b
		if even > 0:
			ans += a
	elif a <= 0 and b <= 0:
		if even == 0:
			ans += b
		else:
			ans += a
	print(ans)


import math

def prime_factors(n):
	factors = []
	while n % 2 == 0:
		n //= 2
		factors.append(2)
	for i in range(3, int(math.sqrt(n) + 1), 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def solve(n, a, b):
	(even, odd) = (0, 0)
	for div in factors:
		if div % 2 == 0:
			even += 1
		else:
			odd += 1
	return (even, odd)
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	factors = prime_factors(n)
	score = 0
	(even, odd) = solve(n, a, b)
	if a >= 0 and b >= 0:
		score = a * even + b * odd
	elif a >= 0 and b < 0:
		if even:
			score = a * even
		else:
			score = b
	elif a < 0 and b >= 0:
		if odd:
			score = b * odd
		if even:
			score += a
	elif even:
		score = a
	else:
		score = b
	print(score)


def solve(n, a, b):
	i = 2
	even = 0
	odd = 0
	while i * i <= n:
		while n % i == 0:
			n = n // i
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
		i += 1
	ans = 0
	if n > 1:
		if n % 2 == 0:
			even += 1
		else:
			odd += 1
	if a >= 0 and b >= 0:
		ans = even * a + odd * b
	elif a >= 0 and b < 0:
		if even:
			ans = even * a
		elif odd:
			ans = b
	elif a < 0 and b >= 0:
		if odd:
			ans = odd * b
		if even:
			ans += a
	elif a < 0 and b < 0:
		if even:
			ans = a
		elif odd:
			ans = b
	print(ans)

def main():
	for i in range(int(input())):
		(n, a, b) = map(int, input().split())
		solve(n, a, b)
main()


import math
for _ in range(int(input())):
	(n, a, b) = map(int, input().strip().split())
	(x, p) = (3, 0)
	(od, ev) = (0, 0)
	if n % 2 == 0:
		while n % 2 == 0:
			n = n // 2
			ev += 1
	while n > 1 and x <= math.ceil(math.sqrt(n)) + 1:
		if n % x == 0:
			while n % x == 0:
				n = n // x
				od += 1
		x += 2
	if n > 2:
		od += 1
	if a >= 0 and b >= 0:
		c = ev * a + od * b
	elif a >= 0 and b < 0:
		c = ev * a if ev else b
	elif a < 0 and b >= 0:
		c = min(1, ev) * a + od * b
	else:
		c = a if ev > 0 else b
	print(c)


from collections import Counter
import math

def pf(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			a.append(i)
			n = n / i
	if n > 2:
		a.append(int(n))
	return a
for t in range(int(input())):
	(n, a, b) = map(int, input().split())
	d = pf(n)
	c = Counter(d)
	x = 0
	o = 0
	e = 0
	for i in c.keys():
		if i % 2:
			o += c[i]
		else:
			e += c[i]
	if a >= 0 and b >= 0:
		x = e * a + o * b
	elif a <= 0 and b <= 0:
		if n % 2:
			x = b
		else:
			x = a
	elif a >= 0 and b <= 0:
		if n % 2:
			x = b
		else:
			x = e * a
	elif a <= 0 and b >= 0:
		if n % 2:
			x = o * b
		else:
			x = o * b + a
	print(x)


from math import sqrt
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	N = n
	count_even = 0
	count_odd = 0
	while n % 2 == 0:
		count_even += 1
		n //= 2
	i = 3
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			count_odd += 1
			n = n // i
	if n > 1:
		if n % 2 == 0:
			count_even += 1
		else:
			count_odd += 1
	if a >= 0 and b >= 0:
		print(a * count_even + b * count_odd)
	elif a >= 0 and b < 0:
		if count_even > 0:
			print(a * count_even)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if count_even == 0:
			print(b * count_odd)
		else:
			print(b * count_odd + a)
	elif N % 2 == 0:
		print(a)
	else:
		print(b)


import io, os, time
from sys import stdin, stdout

def take_input():
	s = stdin.readline()
	return s

def display_arr(arr):
	stdout.write(' '.join(map(str, arr)) + '\n')

def display_num(num):
	stdout.write(str(num) + '\n')
for _ in range(int(take_input())):
	(n, a, b) = map(int, take_input().split())
	(even, odd) = (0, 0)
	i = 2
	while i * i <= n:
		while n % i == 0:
			n = n // i
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
		i += 1
	if n > 1:
		if n % 2 == 0:
			even += 1
		else:
			odd += 1
	ans = 0
	if a >= 0 and b >= 0:
		ans = even * a + b * odd
	if a >= 0 and b < 0:
		if even:
			ans = a * even
		else:
			ans = b
	if a < 0 and b >= 0:
		ans = b * odd
		if even:
			ans += a
	if a < 0 and b < 0:
		if even:
			ans = a
		else:
			ans = b
	print(ans)


import math

def pr(n):
	d = {}
	while n % 2 == 0:
		if 2 in d:
			d[2] += 1
		else:
			d[2] = 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
			n = n // i
	if n > 2:
		d[n] = 1
	return d

def solve():
	(n, a, b) = map(int, input().split())
	d = pr(n)
	ans = 0
	two = 0
	if 2 in d:
		two = d[2]
	rest = sum(d.values()) - two
	if a >= 0 and b >= 0:
		ans = a * two + b * rest
	elif a >= 0 and b < 0:
		ans = a * two
		if not two:
			ans = b
	elif a < 0 and b >= 0:
		ans = b * rest
		ans = ans + (a if two else 0)
	else:
		ans = a if two else b
	print(ans)
for testis in range(int(input())):
	solve()


from sys import stdin
import math
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	even = 0
	odd = 0
	if a % 2 == 0:
		count = 0
		while a % 2 == 0:
			a = a // 2
			count += 1
		even += count
	for k in range(3, int(math.sqrt(a)) + 1, 2):
		if a % k == 0:
			count = 0
			while a % k == 0:
				a = a // k
				count += 1
			odd += count
	if a != 1 and a > 2:
		odd += 1
	if b >= 0 and c >= 0:
		print(even * b + odd * c)
	elif b >= 0 and c <= 0:
		if even != 0:
			print(even * b)
		else:
			print(c)
	elif b <= 0 and c >= 0:
		if even != 0:
			print(b + odd * c)
		else:
			print(odd * c)
	elif b <= 0 and c <= 0:
		if even != 0:
			print(b)
		else:
			print(c)


t = int(input())
for i in range(t):
	(n, a, b) = list(map(int, input().split()))
	even = 0
	odd = 0
	while n % 2 == 0:
		even += 1
		n = n // 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
				odd += 1
		i += 1
	if n != 1:
		odd += 1
	if a >= 0 and b >= 0:
		print(even * a + odd * b)
	elif a <= 0 and b <= 0:
		if even != 0:
			print(a)
		else:
			print(b)
	elif a <= 0 and b >= 0:
		if even != 0:
			print(odd * b + a)
		else:
			print(odd * b)
	elif even != 0:
		print(even * a)
	else:
		print(b)


import math

def primeFactors(n):
	cnt1 = 0
	lst = []
	while n % 2 == 0:
		lst.append(2)
		cnt1 += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			(lst.append(i),)
			n = n / i
	if n > 2:
		lst.append(n)
	return (cnt1, len(lst) - cnt1, lst)
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	(cnt1, cnt2, lst) = primeFactors(n)
	if a >= 0 and b >= 0:
		val = a * cnt1 + b * cnt2
	elif a >= 0 and b < 0:
		if cnt1 > 0:
			val = a * cnt1
		else:
			val = b
	elif a < 0 and b >= 0:
		if cnt1 > 0:
			val = b * cnt2 + a
		else:
			val = b * cnt2
	elif cnt1 > 0:
		val = a
	else:
		val = b
	print(val)


from math import sqrt
import math
import math

def primeFactors(n):
	count1 = 0
	count2 = 0
	while n % 2 == 0:
		count1 += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			count2 += 1
			n = n // i
	if n > 2:
		count2 += 1
	return (count1, count2)
t = int(input())
for _ in range(t):
	(n, a, b) = list(map(int, input().split()))
	(c1, c2) = primeFactors(n)
	if a >= 0 and b >= 0:
		print(c1 * a + c2 * b)
	elif a >= 0 and b < 0:
		if c1 > 0:
			print(c1 * a)
		else:
			print(b)
	elif a < 0 and b >= 0:
		if c1 > 0:
			print(a + c2 * b)
		else:
			print(c2 * b)
	elif c1:
		print(a)
	else:
		print(b)


from math import sqrt
prime = []
siev = [0 for _ in range(int(sqrt(pow(10, 9))) + 1)]
siev[0] = 1
siev[1] = 1
for i in range(len(siev)):
	if siev[i] == 0:
		prime.append(i)
		j = 2
		while i * j < len(siev):
			siev[i * j] = 1
			j = j + 1
for _ in range(int(input())):
	ans = 0
	(n, a, b) = map(int, input().split())
	(even, odd) = (0, 0)
	for i in prime:
		while n % i == 0:
			n = n / i
			if i == 2:
				even = even + 1
			else:
				odd = odd + 1
		if n == 1:
			break
	if n != 1:
		odd = odd + 1
	if a >= 0 and b >= 0:
		ans = a * even + b * odd
	elif a < 0 and b >= 0:
		ans = ans + b * odd
		if even:
			ans = ans + a
	elif a >= 0 and b < 0:
		if even:
			ans = even * a
		else:
			ans = b
	elif even:
		ans = a
	else:
		ans = b
	print(ans)


import math
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	e = 0
	o = 0
	while n % 2 == 0:
		e += 1
		n /= 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			o += 1
			n /= i
	if n > 2:
		o += 1
	ans = 0
	if a >= 0 and b >= 0:
		ans = a * e + b * o
	elif a < 0 and b >= 0:
		ans = b * o + a * min(1, e)
	elif a >= 0 and b < 0:
		if e > 0:
			ans = a * e
		else:
			ans = b
	elif a < 0 and b < 0:
		if e > 0:
			ans = a
		else:
			ans = b
	print(ans)


def Fact(x):
	(e, o) = (0, 0)
	while not x & 1:
		x //= 2
		e += 1
	i = 3
	while i * i <= x:
		while not x % i:
			x //= i
			o += 1
		i += 2
	if x > 2:
		o += 1
	return (e, o)
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	(e, o) = Fact(n)
	if n & 1:
		if b < 0:
			o = 1
	else:
		if a < 0:
			e = 1
		if b < 0:
			o = 0
	print(o * b + a * e)


def primes(num):
	(e, o) = (0, 0)
	while num % 2 == 0:
		e += 1
		num //= 2
	i = 3
	while i * i <= num:
		while num % i == 0:
			o += 1
			num //= i
		while num % (i + 2) == 0:
			o += 1
			num //= i + 2
		i += 2
	if num > 2:
		o += 1
	return (e, o)
for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	(evens, odds) = primes(n)
	if n % 2 == 0:
		if a <= 0 and b <= 0:
			print(a)
		elif a < 0 and b > 0:
			print(a + odds * b)
		elif a > 0 and b < 0:
			print(evens * a)
		elif a >= 0 and b >= 0:
			print(a * evens + b * odds)
	elif b >= 0:
		print(b * odds)
	else:
		print(b)


def evenprimes(num):
	count = 0
	while num % 2 == 0:
		count += 1
		num //= 2
	return (num, count)

def oddprimes(num):
	count = 0
	while num % 3 == 0:
		count += 1
		num //= 3
	i = 5
	while i * i <= num:
		while num % i == 0:
			count += 1
			num //= i
		while num % (i + 2) == 0:
			count += 1
			num //= i + 2
		i += 6
	if num > 3:
		count += 1
	return count
t = int(input())
while t != 0:
	(n, a, b) = map(int, input().split())
	(n1, evens) = evenprimes(n)
	odds = oddprimes(n1)
	if n % 2 == 0:
		if a <= 0 and b <= 0:
			print(a)
		elif a < 0 and b > 0:
			temp = a + odds * b
			print(temp)
		elif a > 0 and b < 0:
			print(evens * a)
		elif a >= 0 and b >= 0:
			temp = a * evens + b * odds
			print(temp)
	elif b >= 0:
		print(b * odds)
	else:
		print(b)
	t -= 1


import math
x = int(input())
for i in range(x):
	y = input().split()
	n = int(y[0])
	a = int(y[1])
	b = int(y[2])
	count = 0
	z = int(math.sqrt(n))
	even = 0
	odd = 0
	flag = False
	if n & 1 == 0:
		flag = True
	if a >= 0 and b >= 0:
		while n % 2 == 0:
			n = n / 2
			even += 1
		for j in range(3, z + 1, 2):
			while n % j == 0:
				n = n / j
				odd += 1
			j += 1
		if n > 2:
			odd += 1
		print(a * even + b * odd)
	elif a >= 0 and b < 0:
		if n & 1 == 0:
			while n % 2 == 0:
				n = n / 2
				even += 1
			print(a * even)
		else:
			print(b * 1)
	elif a < 0 and b >= 0:
		if n & 1 == 0:
			even += 1
		while n % 2 == 0:
			n = n / 2
		for j in range(3, z + 1, 2):
			while n % j == 0:
				n = n / j
				odd += 1
			j += 1
		if n > 2:
			odd += 1
		print(even * a + b * odd)
	elif a < 0 and b < 0:
		if n & 1 == 0:
			even += 1
		else:
			odd += 1
		print(a * even + b * odd)


def function(n, a, b):
	(even, odd) = (0, 0)
	i = 2
	while i * i <= n:
		while n % i == 0:
			n //= i
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
		i += 1
	if n > 1:
		if n % 2 == 0:
			even += 1
		else:
			odd += 1
	if a >= 0 and b >= 0:
		result = even * a + odd * b
	elif a >= 0 and b < 0:
		if even > 0:
			result = even * a
		else:
			result = b
	elif a < 0 and b >= 0:
		result = odd * b
		if even > 0:
			result += a
	elif a < 0 and b < 0:
		if even:
			result = a
		else:
			result = b
	return result
tc = int(input())
for _ in range(tc):
	(n, a, b) = map(int, input().split())
	print(function(n, a, b))


from math import floor
m = 10 ** 5
lp = list(range(m))
pr = []
for i in range(2, m):
	if lp[i] == i:
		pr.append(i)
	j = 0
	while j < len(pr) and pr[j] <= lp[i] and (pr[j] * i < m):
		lp[i * pr[j]] = pr[j]
		j += 1
for t in range(int(input())):
	(n, a, b) = tuple(map(int, input().strip().split()))
	ec = 0
	while n % 2 == 0:
		n //= 2
		ec += 1
	oc = 0
	i = 1
	sqrt_n = floor(n ** 0.5)
	while pr[i] <= sqrt_n:
		p = pr[i]
		while n % p == 0:
			n //= p
			oc += 1
		i += 1
	if n != 1:
		oc += 1
	ans = 0
	if a < 0:
		ans += a * min(1, ec)
	else:
		ans += a * ec
	if b < 0:
		ans += b * min(0 if ec > 0 else 1, oc)
	else:
		ans += b * oc
	print(ans)


import sys

def generatePrimeFactors(n):
	k = n
	e = 0
	o = 0
	while n % 2 == 0:
		e = e + 1
		n = n // 2
	for i in range(3, int(k ** 0.5) + 1, 2):
		while n % i == 0 and n > 1:
			o = o + 1
			n = n // i
		if n == 1:
			break
	if n != 1:
		o = o + 1
	return [e, o]
for _ in range(int(sys.stdin.readline())):
	(n, a, b) = map(int, sys.stdin.readline().split())
	l = generatePrimeFactors(n)
	ar = l[0]
	c = l[1]
	if a >= 0 and b >= 0:
		print(a * ar + c * b)
	elif a >= 0 and b < 0:
		if ar == 0:
			print(b)
		else:
			print(ar * a)
	elif a < 0 and b >= 0:
		if ar == 0:
			print(b * c)
		else:
			print(a + b * c)
	elif ar == 0:
		print(b)
	else:
		print(a)


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
from collections import defaultdict

def divs(n):
	d = defaultdict(int)
	while n % 2 == 0:
		n //= 2
		d[2] += 1
	for j in range(3, int(n ** 0.5) + 1, 2):
		while n % j == 0:
			n //= j
			d[j] += 1
	if n > 1:
		d[n] += 1
	return d
for _ in range(*maps()):
	(n, a, b) = maps()
	d = divs(n)
	(even, odd) = (0, 0)
	for i in d:
		if i % 2:
			odd += d[i]
		else:
			even += d[i]
	ans = 0
	if a >= 0 and b >= 0:
		ans = a * even + b * odd
	if a >= 0 and b <= 0:
		ans = a * even if n % 2 == 0 else b
	if a <= 0 and b >= 0:
		ans = b * odd if n % 2 else odd * b + a
	if a <= 0 and b <= 0:
		ans = a if n % 2 == 0 else b
	print(ans)


for _ in range(int(input())):
	(N, A, B) = map(int, input().split())
	prime_factors = {}
	if A < 0 and B < 0:
		print(B if N % 2 else A)
		continue
	while N > 1 and N % 2 == 0:
		prime_factors.setdefault(2, 0)
		prime_factors[2] += 1
		N //= 2
	for i in range(3, int(N ** 0.5) + 1, 2):
		while N > 1 and N % i == 0:
			prime_factors.setdefault(i, 0)
			prime_factors[i] += 1
			N //= i
	if N > 1:
		prime_factors[N] = 1
	if A >= 0 and B >= 0:
		val = 0
		for reps in prime_factors:
			if reps % 2:
				val += prime_factors[reps] * B
			else:
				val += prime_factors[reps] * A
		print(val)
	elif A >= 0:
		print(prime_factors.get(2, 0) * A if prime_factors.get(2, 0) else B)
	elif B >= 0:
		print((sum(prime_factors.values()) - prime_factors.get(2, 0)) * B + (A if prime_factors.get(2, 0) else 0))


import math

def primeFactors(n):
	lis = []
	while n % 2 == 0:
		lis.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			lis.append(i)
			n = n / i
	if n > 2:
		lis.append(n)
	return lis
for _ in range(int(input())):
	(N, A, B) = map(int, input().split())
	ev = []
	od = []
	s = 0
	k = primeFactors(N)
	for i in k:
		if i % 2 == 0:
			ev.append(i)
		else:
			od.append(i)
	if A <= 0 and B <= 0:
		if N % 2 == 0:
			print(A)
		else:
			print(B)
	elif A > 0 and B > 0:
		s = len(ev) * A + len(od) * B
		print(s)
	elif A > 0 and B <= 0:
		if len(ev) > 0 and len(od) > 0:
			s = len(ev) * A
			print(s)
		else:
			s = len(ev) * A
			if len(od) > 0:
				s += B
			print(s)
	elif A <= 0 and B > 0:
		if len(ev) > 0 and len(od) > 0:
			s = len(od) * B + A
			print(s)
		else:
			s = len(od) * B
			if len(ev) > 0:
				s += A
			print(s)


import math

def pfs(n):
	resE = 0
	resO = 0
	while n % 2 == 0:
		resE += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			resO += 1
			n = n / i
	if n > 2:
		if n % 2 == 0:
			resE += 1
		else:
			resO += 1
	return (resE, resO)
t = int(input())
for i in range(t):
	nab = input().split()
	n = int(nab[0])
	a = int(nab[1])
	b = int(nab[2])
	(pfE, pfO) = pfs(n)
	ans = 0
	if a >= 0 and b >= 0:
		ans = pfE * a + pfO * b
	elif a >= 0 and b < 0:
		if pfE > 0:
			ans = pfE * a
		else:
			ans = b
	elif a < 0 and b >= 0:
		ans = pfO * b
		if pfE > 0:
			ans += a
	elif pfE > 0:
		ans = a
	else:
		ans = b
	print(ans)


def solve(n, a, b):
	res = 0
	(even_count, odd_count) = (0, 0)
	i = 2
	while i * i <= n:
		while n % i == 0:
			n //= i
			if i % 2 != 0:
				odd_count += 1
			else:
				even_count += 1
		i += 1
	if n > 1:
		if n % 2 != 0:
			odd_count += 1
		else:
			even_count += 1
	if a >= 0 and b >= 0:
		return a * even_count + b * odd_count
	elif a >= 0 and b < 0:
		if even_count > 0:
			return a * even_count
		elif odd_count > 0:
			return b
	elif a < 0 and b >= 0:
		res = b * odd_count
		if even_count > 0:
			return res + a
		return res
	elif a < 0 and b < 0:
		if even_count > 0:
			return a
		elif odd_count > 0:
			return b
for _ in range(int(input())):
	l = list(map(int, input().strip().split()))
	(n, a, b) = (l[0], l[1], l[2])
	print(solve(n, a, b))


t = int(input())
for tc in range(t):
	(n, a, b) = map(int, input().split())
	odd = 0
	even = 0
	ans = 0
	i = 2
	while i * i <= n:
		while n % i == 0:
			n //= i
			if i % 2 != 0:
				odd += 1
			else:
				even += 1
		i += 1
	if n > 1:
		if n % 2 != 0:
			odd += 1
		else:
			even += 1
	if a >= 0 and b >= 0:
		print(a * even + b * odd)
		continue
	elif a >= 0 and b < 0:
		if even:
			ans = a * even
		elif odd:
			ans = b
	elif a < 0 and b >= 0:
		ans = b * odd
		if even:
			ans += a
	elif a < 0 and b < 0:
		if even:
			ans += a
		elif odd:
			ans += b
	print(ans)


import math
primes = []
sieve = [0 for i in range(int(math.sqrt(10 ** 9)))]
for i in range(2, int(math.sqrt(10 ** 9))):
	if sieve[i] == 0:
		primes.append(i)
		for j in range(i + i, int(math.sqrt(10 ** 9)), i):
			sieve[j] += 1
for t in range(int(input())):
	(n, a, b) = map(int, input().split())
	p = n
	even = 0
	evensum = 0
	odd = 0
	oddsum = 0
	if a <= 0 and b <= 0:
		if p % 2 == 0:
			print(a)
		else:
			print(b)
		continue
	while n > 1 and n % 2 == 0:
		n = n // 2
		even += 1
	for i in primes:
		while n > 1 and n % i == 0:
			odd += 1
			n = n // i
		if n <= 1:
			break
	if n > 1:
		odd += 1
	if a < 0:
		cost = odd * b
		if p % 2 == 0:
			cost += a
		print(cost)
	elif b < 0:
		cost = even * a
		if p % 2 == 1:
			cost += b
		print(cost)
	else:
		print(odd * b + even * a)


import math
t = int(input())
while t > 0:
	(n, a, b) = input().split(' ')
	(n, a, b) = (int(n), int(a), int(b))
	pt1 = 0
	pt2 = 0
	while n % 2 == 0:
		pt1 += 1
		n = n // 2
	for i in range(3, int(math.sqrt(n) + 1), 2):
		if i == 2:
			while n % i == 0:
				pt += 1
				n = n // i
		else:
			while n % i == 0:
				pt2 += 1
				n = n // i
	if n > 1:
		pt2 += 1
	ans = 0
	ans = pt1 * a + pt2 * b
	if pt2 > 0 and pt1 > 0:
		ans = max(ans, a + b)
		ans = max(ans, a * pt1 + b)
		ans = max(ans, a)
		ans = max(ans, a * pt1)
		ans = max(ans, a + b * pt2)
	if pt1 > 0:
		ans = max(ans, pt1 * a)
		ans = max(ans, a)
	if pt1 == 0:
		if pt2 > 0:
			ans = max(ans, b)
			ans = max(ans, pt2 * b)
	print(ans)
	t -= 1